递归的概念
1.基本概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
2.基本要求
看到递归算法的定义，首先注意到的就是调用自身这个特点，个人感觉这和循环非常类似。开始循环的基本要求是初始化表达式、循环控制语句和增值表达式。递归中的初始的输入可对应初始化表达式，其本身对输入的改变可以看做是增值表达式。还差一个循环控制语句，也就是停止递归的条件，递归算法递归到最后一次时可以直接得到想要的值而不需要再次调用自身，这种操作就可以对应为循环控制语句。
经典样例
1.Fibonacci数列
无穷数列1,1,2,3,5,8,13,21,34,55,···称为Fibonacci数列。其中，第3位数是第1位数和第2位数的和，第4位数是第2位数和第3位数的和···也就是说，当\(n{geq}2\)时，第\(n\)位数是第\(n-1\)位数和第\(n-2\)位数的和，即
这个函数具有调用自身的特点，且具有停止递归的条件（\(F(0)=1,F(1)=1\)），所以该函数是一个递归函数。该问题递归算法如下：
int factorial(int n){
if (n == 0)
return 1;
return n*factorial(n-1);
}
2.Hanoi塔问题
设\(a、b、c\)是三个塔座。开始时，在塔座\(a\)上有一叠共\(n\)个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为\(1,2,\cdots,n\)，现要求将塔座\(a\)上的这一叠圆盘移到塔座\(b\)上，并仍按同样的顺序叠置。在移动圆盘是应遵守以下移动规则：
规则Ⅰ：每次只能移动一个圆盘；
规则Ⅱ：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则Ⅲ：在满足移动规则Ⅰ和Ⅱ的前提下，可将圆盘移至\(a、b、c\)中任一塔座上。
当\(n=1\)时，只要将编号为\(1\)的圆盘从塔座\(a\)移到塔座\(b\)上即可。当\(n>1\)时，只要设法将\(n-1\)个较小的圆盘移至塔座\(c\)上，再将第\(n\)个圆盘移至塔座\(b\)上，之后再设法将\(n-1\)个较小的圆盘移至塔座\(b\)上即可。由此可见，\(n\)个圆盘的移动问题可以分为两次\(n-1\)个圆盘移动的问题，而后者又可以分为两次\(n-2\)个圆盘移动的问题，一直调用自身直到最后变为移动\(1\)个圆盘的问题，而这个问题可以直接给出答案，也就是停止递归的条件。该问题递归算法如下：
void hanoi(int n, int a, int b, int c){
if (n>0){
hanoi(n-1, a, b, c);
move(a, b);
hanoi(n-1, c, b, a);
}
}
传说中Hanoi塔梵天穿好的那根针上一共有\(64\)个圆盘，当所有的圆盘都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭。假设移动一个圆盘需要\(1\)秒，按照上述递归算法，移动这些圆盘需要\(18446744073709551615\)秒，到那时，除非有现实版流浪地球，否则地球早被红巨星化的太阳吞噬了，看来传说所言非虚。
递归的实现
递归算法在执行时需要多次调用自身，实现这种递归调用的关键是为算法建立递归调用工作栈。通常在一个算法中调用另一个算法，系统需在运行被调用算法之前完成三件事：
\(~~~~\)1.将所有实参指针、返回地址等信息传递给被调用算法；
\(~~~~\)2.为被调用算法的局部变量分配存储区；
\(~~~~\)3.将控制转移到被调用算法的入口。
在从被调用算法返回调用算法时，系统也需在那之前完成三件事：
\(~~~~\)1.保存被调用算法的计算结果；
\(~~~~\)2.释放分配给被调用算法的数据区；
\(~~~~\)3.依照被调用算法保存的返回地址将控制权转移到调用算法。
当多个算法构成嵌套时，系统将整个程序运行时所需的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法，就释放它在栈顶的存储区。
递归算法的实现就是这样的过程，只不过调用和被调用的算法是同一个算法。若调用一个递归算法的主算法为第0层算法，则从主算法调用递归算法为进入第1层调用；从第\(i\)层递归调用本算法为进入第\(i+1\)层调用。反之，退出第\(i\)层递归调用，则返回至第\(i-1\)层调用。为了保证递归调用正确执行，系统要建立一个递归调用工作栈，为各层次的调用分配数据存储区。每层递归调用所需的信息构成一个工作记录，其中包括所有实参指针、所有局部变量以及返回上一层的地址。每进入一层递归调用，就产生一个新的工作记录压入栈顶。每退出一层递归调用，就从栈顶弹出一个工作记录。
递归的优缺
递归算法结构清晰，可读性强，且容易用数学归纳法证明算法的正确性。递归技术往往使函数的定义和算法的描述简洁且易于理解。但是递归算法的运行效率较低，时间复杂性和空间复杂性都大于非递归算法。
因此，有时希望在递归算法中消除递归调用，使其转化为一个非递归算法。通常，消除递归采用一个用户定义的栈来模拟系统的递归调用工作栈，从而达到将递归算法改为非递归算法的目的。仅仅是机械地模拟还不能达到缩短计算时间和减小存储空间的目的，还需要根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。