递归： 在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。 通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。
1. 什么问题可以用递归算法来解决
1.1 定义是递归的
比如很多数学定义是递归的，比如阶乘、斐波那契数列，卢卡斯数列等。对于类似的复杂问题，若能拆分为几个简单的相同或类似的子问题来求解，便称为递归求解。
- 1.能将问题转变成一个个的小问题，新问题和原问题的解法相同或类似；
- 2.可以通过第一条的转换使得问题简化；
- 3.必须有一个明确的递归出口（边界）。
// 阶乘 10！= 10*9！
int Fact(int n) {
if (n == 0) {
return 1;
} else {
return n*Fact(n-1);
}
}
// 斐波那契
int Fbi(int n){
if (n<1) {
return 0;
} else if (n<3){
return 1;
} else {
return Fbi(n-1) + Fbi(n-2);
}
}
1.1 数据结构是递归的
其数据结构本身具有递归的特性，例如链表，通过指针指向下一个节点，所以在节点中包含了自身。
示例：(打印链表内的所有元素)
void TraverseList(LinkList p) {
// 递归终止
if (p == NULL) { return; }
// 输出当前节点的数据
printf("%d",p->data);
// 指向下一个节点继续打印
TraverseList(p->next);
}
在递归算法中，如果当递归结束条件成立只执行return操作时，分治法求解递归问题算法一般形式可以简化为：
void p(arg…){
if (递归结束条件不成立) {
p(分解的参数);
}
}
void TraverseList(LinkList p) {
// 递归终止
if (p) {
// 输出当前节点的数据
printf("%d",p->data);
// 指向下一个节点继续打印
TraverseList(p->next);
}
}
1.3 问题的解法是递归的
有些问题虽然本身没有明显的递归结构，但是采样递归求解比迭代求解更简单，比如汉诺塔问题，皇后问题，迷宫问题
2. 递归过程与递归工作栈
一个递归函数在其执行过程中，需要多次进行自我调用，那么递归函数是如何执行的呢？
函数调用： 在高级语言的程序中，函数的调用都是通过栈来进行的。通常在一个函数的运行期间调用另一个函数时，在运行被调用函数之前系统一般需要完成3件事情：
- 1.将所有的实参，返回地址等信息放入被调用函数的栈空间（寄存器X0...X30，不同架构一样）
- 2.为被调用函数的局部变量分配存储空间
- 3.将控制权限转移至被调用函数的入口
从被调用函数返回需要调用函数之前，系统同样需要完成3件事
- 1.保存被调用函数的结果
- 2.释放函数内的临时变量更数据区的内存
- 3.根据返回地址将控制权移动到调用函数
当多个函数构成嵌套调用时，按照先调用后返回的原则，上述函数之间的信息传递和控制转移则需要通过栈来实现，即系统将整个程序运行时所需要的数据空间都安排在一个栈中，每当调用一个函数的时候，就在它的栈顶分配一个存储区域，每当这个函数退出时，就释放它的存储区域，从而回到调用函数栈区的栈顶。
示例：
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int r = add1(1, 3);
printf("计算结果是%d",r);
return 0;
}
int add1(int a, int b) {
int t = add2(a, b);
return t;
}
int add2(int d, int e) {
int t = 2;
return d+e+t;
}
通过汇编看函数调用栈：
一个递归函数的运行过程类似多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此和每次调用相关的一个重要概念是递归函数运行的运行“层次”，假设调用该递归函数的主函数为第0层，则从主函数调用递归函数进入第1层，以后每调用一次就加一层，每返回一层就减一层，直至返回到主函数。
为了保证递归函数正确执行，系统需要设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区，每一层递归所需信息构成一个工作记录，其中包括所有的实参，所有的局部变量，以及上一层的返回地址，每进入一层递归就产生一个新的工作记录压入栈顶，每退出一个递归就从栈顶弹出一个工作记录，则当前执行层的工作记录称为“活动记录”。
本质上讲呢，在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，占用内存就越多，就会导致栈溢出。
3.使用递归思想解决汉诺塔问题
3.1 汉诺塔问题简介(摘自百度百科)
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
3.2 问题分析
假设柱子编号分别为A、B、C，盘子的个数为n，我们要做的是将A上的所有盘子按照规则移动到C柱上，B柱作为辅助柱。计算移动次数。
- 当n=1，即只有一个盘子的时候，只需将将这个盘子直接放到C柱即可；
- 当n=2时，只需将第一个盘子放到B上，第二个盘子放到C柱，然后将B上的放到C上即可；
-
当n>2时，我们可以把问题简化为第n个盘子和其上面的盘子的关系，就像一直有两个盘子，我们完成两个盘子的移动就可以了。把问题拆解开来就是n和n-1的关系，直至n=2。也就是 我们先把上方的63个盘子看成整体，这下就等于只有两个盘子，现在我们先不管第64个盘子，假设A柱只有63个盘子，与之前一样的解决方式，前62个盘子先完成移动目标。然后前62,61,60，......，2,1，最终，最上方的盘子是可以直接移动到c柱的，那就好办了，我们的2号盘也能完成向c柱的转移，这时c柱上时已经转移成功的2个盘，于是3号盘也可以了，一直到第64号盘。
初始状态.png
-
3.3 代码实现（C语言）
int count = 0;
// 移动某个盘子至某个位置
void Move(char X, char Y, int t) {
count++;
printf("%d: from %c ——> %c \n",t,X,Y);
}
// 将塔盘A上的圆盘按规则移动到塔盘C上,B作为辅助塔盘;
// n为当前盘子编号. ABC为塔盘，
void Hanoi(int n, char A, char B, char C) {
if (n == 1) {
Move(A, C, 1);
} else {
// 将塔盘A上的编号为1至n-1的圆盘移动到塔盘B上,C作为辅助塔;
Hanoi(n-1, A, C, B);
// 将编号为n的圆盘从A移动到C上;
Move(A, C, 1);
// 将塔盘B上的编号为1至n-1的圆盘移动到塔盘C上,A作为辅助塔;
Hanoi(n-1, B, A, C);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int n;
printf("请输入要移动的盘子的个数：");
scanf("%d",&n);
Hanoi(n, 'A', 'B', 'C');
printf("移动%d个盘子需要移动%d次",n,count);
return 0;
}
