常见的递归算法

计算阶乘

//计算阶乘
int factorial(int n){
    if (n < 2) return 1;
    return n*factorial(n-1);
}

//简化写法
int factorial_1(int n){
    return (n < 2) ? 1 : n*factorial(n-1);
}

 计算前n项和

//计算1+2+3+...+n
int sum(int n){
    if(n == 0) return 0;
    return n+sum(n-1);
}

//简化写法
int sum_1(int n){
    return (n == 0) ? n : n+sum(n-1);
}

斐波那契数列

//斐波那契数列
int fibonacci(int n){
    if(n < 2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

//简化写法
int fibonacci_1(int n){
    return (n < 2) ? n : fibonacci(n-1) + fibonacci(n-2);
}

汉诺塔问题

//汉诺塔
void hanoiTower(int n, char a = 'A', char b = 'B', char c = 'C'){
    if(n == 1) cout << "move from " << a << " to " << c << "." << endl;
    else{
        hanoiTower(n-1,a,c,b);
        hanoiTower(1,a,b,c);
        hanoiTower(n-1,b,a,c);    
    }
}

其实汉诺塔问题用递归是很容易解决的

如图要将n个盘子从a柱子移动到c柱子而且在整个移动的过程中都要保证大盘子在下，小盘子在上。

整个问题可以拆解成三部分

1. 将n-1个盘子从a移到b

2. 将a上剩余的一个盘子移动到c

3. 最后将b上的n-1个盘子从b移动到c

用C++代码描述这一过程如下所示（采用函数递归方法）

#include <iostream>
#include <fstream>
using namespace std;
int move_steps = 0;

//汉诺塔的移动问题
void move(ofstream &oF, int height = 1, char a = 'A', char b = 'B', char c = 'C'){
	if (height == 1){
		//一个盘子直接从a移到c
		oF << "Move plate from " << a << " to " << c << '.' << endl;
		move_steps++;
	}
	else{
		//先将n-1个盘子从a移到b
		move(oF, height - 1, a, c, b);
		//再将剩余的一个盘子从从a移到c
		move(oF, 1, a, b, c);
		//再将其余的n-1个盘子从b移到c
		move(oF, height - 1, b, a, c);
	}
}

int main(void){
	//创建一个txt文件保存移动步骤
	ofstream of("hanoiTower.txt");
	int height;
	cout << "请输入汉诺塔的层数：";
	cin >> height;
	//调用函数
	move(of, height);
	cout << "一共移动了" << move_steps << "步" << endl;
	of << "\n一共移动了" << move_steps << "步" << endl;
	//关闭文件
	of.close();
	system("pause");
	return 0;
}

测试

当一个盘子的时候

输入

文件内容

当三个盘子的时候

当5个盘子的时候

当10个盘子的时候

可知当盘子的数量为n(n>=1)时，移动的步数2的n次方-1

4399上有小游戏可以提供验证移动的过程