数据结构与算法（6）--递归
Ch6 递归算法
0x01 递归
递归：若一个算法直接或间接的调用自己本身，则称这个算法是递归算法。
存在算法调用自己的情况：
- 问题的定义是递归的（如阶乘函数）
- 问题的解法存在自调用（如在一个有序数组中查找一个数据元素是否存在的折半查找算法）
例子1:阶乘函数
#include<iostream>
using namespace std;
long int Fact(int n)
{
long int x;
if (n < 0) //n < 0时阶乘无定义
{
cout<<"参数错！"<<endl;
return -1;
}
if (n == 0) return 1;
else {
x = Fact(n - 1); //递归调用
return n * x;
}
}
主函数
int main()
{
long int fn,fn2;
fn = Fact(3);
fn2 = Fact(5);
cout << fn << " "<< fn2 << endl;
system("pause");
return 0;
}
结果
6 120
请按任意键继续. . .
例子2：有序数组中查找元素x是否存在的折半查找。
int BSearch(int a[], int x, int low, int high)
{
int mid;
if (low > high) return -1; //查找不成功
mid = (low + high) / 2;
if (x == a[mid]) return mid; //查找成功
else if (x < a[mid])
return BSearch(a, x, low, mid - 1); //在下半区查找
else
return BSearch(a, x, mid + 1, high); //在上半区查找
}
主函数
int main()
{
int a[] = { 1, 3, 4, 5, 17, 18, 31, 33 };
int x = 17;
int bn;
bn = BSearch(a, x, 0, 7);
if (bn == -1) cout<<"x不在数组a中"<<endl;
else cout<<"x在数组a的下标"<< bn <<"中"<<endl;
system("pause");
return 0;
}
结果
x在数组a的下标4中
请按任意键继续. . .
0x02 递归算法的设计方法
基本思想：对于一个较复杂的问题，原问题分解成若干个相对简单且类同的子问题,这样，原问题就可递推得到解。
适用于递归算法求解的问题的充分必要条件是：
（1）问题具有某种可借用的类同自身的子问题描述的性质；
（2）某一有限步的子问题（也称作本原问题）有直接的解存在；
当一个问题存在上述两个基本要素时，该问题的递归算法的设计方法是：
（1）把对原问题的求解设计成包含有对子问题求解的形式。
（2）设计递归出口。
例3 汉诺塔问题。
汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。
基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。
4个盘子汉诺塔问题的递归求解示意图如下所示。
函数如下：
void towers(int n, char fromPeg, char toPeg, char auxPeg)
{
if (n == 1) //递归出口
{
cout<<"move disk 1 from peg "<<fromPeg<<" to peg "<< toPeg<<endl;
return;
}
//把n-1个圆盘从fromPeg借助toPeg移至auxPeg
towers(n - 1, fromPeg, auxPeg, toPeg);
//把圆盘n由fromPeg直接移至toPeg
cout<< "move disk "<<n<<" from peg "<<fromPeg<<" to peg "<<toPeg<<endl;
//把n-1个圆盘从auxPeg借助fromPeg移至toPeg
towers(n - 1, auxPeg, toPeg, fromPeg);
}
主函数
int main()
{
towers(4, \'A\', \'C\', \'B\');
system("pause");
return 0;
}
结果
move disk 1 from peg A to peg B
move disk 2 from peg A to peg C
move disk 1 from peg B to peg C
move disk 3 from peg A to peg B
move disk 1 from peg C to peg A
move disk 2 from peg C to peg B
move disk 1 from peg A to peg B
move disk 4 from peg A to peg C
move disk 1 from peg B to peg C
move disk 2 from peg B to peg A
move disk 1 from peg C to peg A
move disk 3 from peg B to peg C
move disk 1 from peg A to peg B
move disk 2 from peg A to peg C
move disk 1 from peg B to peg C
请按任意键继续. . .
递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束
0x03 递归过程和运行时栈
对于非递归函数，调用函数在调用被调用函数前，系统要保存以下两类信息：
- （1）调用函数的返回地址；
- （2）调用函数的局部变量值。
当执行完被调用函数，返回调用函数前，系统首先要恢复调用函数的局部变量值，然后返回调用函数的返回地址。
递归函数被调用时，系统要做的工作和非递归函数被调用时系统要做的工作在形式上类同，但保存信息的方法不同。
递归函数被调用时，系统的运行时栈也要保存上述两类信息。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为活动记录。
0x04 递归算法的效率分析
以斐波那契数列为例子。
递归实现：
long Fib(int n)
{ if(n == 0 || n == 1) return n; //递归出口
else return Fib(n-1) + Fib(n-2); //递归调用
}
循环实现：
long Fib2(int n)
{ long int oneBack, twoBack, current;
int i;
if(n == 0 || n == 1) return n;
else
{ oneBack = 1;
twoBack = 0;
for(i = 2; i <= n; i++)
{ current = oneBack + twoBack;
twoBack = oneBack;
oneBack = current;
}
return current;
}
}
循环结构的Fib2(n)算法在计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列，因此其时间复杂度为O(n)；
递归结构的Fib(n)算法在计算第n项的斐波那契数列时，必须首先计算第n-1项和第n-2项的斐波那契数列，而某次递归计算得出的斐波那契数列，如Fib(n-1)、Fib(n-2)等无法保存，下一次要用到时还需要重新递归计算，因此其时间复杂度为O(2的n次方) 。
0x05 递归算法到非递归算法的转换
低级程序设计语言（如汇编语言）一般不支持递归，所以需要采用问题的非递归结构算法。
一般来说，存在如下两种情况的非递归算法。
（1）存在不借助堆栈的循环结构的非递归的解决方法，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。这种情况，可以直接选用循环结构的算法。
（2）存在借助堆栈的循环结构的非递归算法，所有递归算法都可以借助堆栈转换成循环结构的非递归算法。（其实就是利用堆栈模拟递归）。两种转换方法：一种方法是借助堆栈，用非递归算法形式化模拟递归算法的执行过程；另一种方法是根据要求解问题的特点，设计借助堆栈的循环结构算法。
0x06 设计举例
例1
从一个有n个人的团体中抽出k (k≤n)个人组成一个委员会，计算共有多少种构成方法。
int Comm(int n, int k)
{
if(n < 1 || k < 0 || k > n) return 0;
if(k == 0) return 1;
if(n == k) return 1;
return Comm(n-1, k-1) + Comm(n-1, k);
}
例2 最大公约数
int Gcd(int n, int m)
{ if(n < 0 || m < 0) exit(0);
if(m == 0) return n;
else if(m > n) return Gcd(m, n);
else return Gcd(m, n % m);
}
回溯法
回溯法是递归算法的一种特殊形式，回溯法的基本思想是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支。搜索一直持续到找到问题的解或者是全部搜索分支都搜索完。