递归算法

null第6章 递归算法第6章 递归算法*6.1 递归的概念 6.2 递归算法的执行过程 6.3 递归算法的设计方法 6.4 递归过程和运行时栈 6.5 递归算法的效率分析 6.6 递归算法到非递归算法的转换 6.7 设计举例6.1递归的概念6.1递归的概念一、在日常生活中，递归一词较常用于描述以自相似方法重复事物的过程。 例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。 *null德罗斯特效应（英语：Droste effect）是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。*null二、在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。 例：第5个人的年龄比第4个的年龄大2岁，有4个人的年龄比第3个的年龄大2岁，有3个人的年龄比第2个的年龄大2岁，有2个人的年龄比第1个的年龄大2岁，第1个的年龄10岁。*null例：阶乘的定义。*null*在下面二种情况中存在算法调用自己的情况：（1）问题的定义是递推的阶乘函数的常见定义是：null*也可定义为：写成函数形式，则为： 这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称上式为阶乘函数的递推定义式。null*（2）问题的解法存在自调用 一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法。 如下例中查找元素17。mid=(low+high)/2　6.2递归算法的执行过程*　6.2递归算法的执行过程 例6-1 给出按照阶乘函数的递推定义式计算阶乘函数的递归算法，并给出n = 3时递归算法的执行过程。 设计：按照阶乘函数的递推定义式计算阶乘函数的递归算法如下： long int Fact(int n) { int x; long int y; if(n < 0) //n < 0时阶乘无定义 { printf(“参数错！”); return -1; }  if(n == 0) return 1; else { y = Fact(n - 1); //递归调用 return n * y; } }null*为说明该递归算法的执行过程，设计调用过程如下：void main(void) { long int fn;   fn = Fact(3); }　 上述代码用实参n = 3调用了递归算法Fact(3)，而Fact(3)要通过调用Fact(2)、Fact(2)要通过调用Fact(1)、Fact(1)要通过调用Fact(0)来得出计算结果。Fact(3)的递归调用过程如下图所示，其中，黑色实线箭头表示函数调用，绿色虚线箭头表示函数返回，此函数在返回时函数名将带回返回值。null*main() …… fn=Fact(3) …… Fact (3) …… y=Fact (2) …… return 3*yFact (2) …… y=Fact(1) …… return 2*y递归调用的执行过程：Fact (1) …… y=Fact(0) …… return 1*yFact (0) …… …… return 1null*　 例6-2 给出在有序数组a中查找数据元素x是否存在的递归算法，并给出折半查找示意图所示实际数据的递归算法的执行过程。 　　设计：算法的参数包括：有序数组a，要查找的数据元素x，数组下界下标low，数组上界下标high。当在数组a中查找到数据元素x时函数返回数组a的下标；当在数组a中查找不到数据元素x时函数返回-1。 null*递归算法如下：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);//在上半区查找 }null*测试代码设计如下： # include   main(void) { int a[] = {1, 3, 4, 5, 17, 18, 31, 33}; int x = 17; int bn;  bn = BSearch(a, x, 0,7); if(bn == -1) printf("x不在数组a中"); else printf("x在数组a的下标%d中", bn); }null*　　BSearch(a, x, 0,7)的递归调用过程如下图所示，其中，实箭头表示过程调用，虚箭头表示过程的返回值。 BSearch(a, x, 0, 7) … mid=3 … return BSearch(a, x, 4, 7)main() … x=17 … bn = BSearch(a, x, 0, 7)BSearch(a, x, 4, 7) … mid=5 … return BSearch(a, x, 4, 4)BSearch(a, x, 4, 4) … mid=4 … return 46.3递归算法的设计方法*6.3递归算法的设计方法　 递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题就可递推得到解。 　null*　 并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题的充分必要条件是： （1）问题具有某种可借用的类同自身的子问题描述的性质； （2）某一有限步的子问题（也称作本原问题）有直接的解存在。null* 当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是： （1）把对原问题的求解设计成包含有对子问题求解的形式。 （2）设计递归出口。null*　 例6-3 设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。　　 问题分析：可以用递归方法求解n个盘子的汉诺塔问题。null*基本思想： 1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。 4个盘子汉诺塔问题的递归求解示意图如下图所示。 null*原柱 A 辅助柱 B 目标柱 C null* 算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,…,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg；最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息： Move Disk i from Peg X to Peg Y 这样，汉诺塔问题的递归算法可设计如下： null*void towers(int n, char fromPeg, char toPeg, char auxPeg) { if(n==1) //递归出口 { printf("%s%c%s%c\n", "move disk 1 from peg ", fromPeg, " to peg ", toPeg); return; } 　 //把n-1个圆盘从fromPeg借助toPeg移至auxPeg towers(n-1,fromPeg,auxPeg,toPeg);  //把圆盘n由fromPeg直接移至toPeg printf("%s%d%s%c%s%c\n", "move disk ", n, " from peg ", fromPeg, " to peg ", toPeg);  //把n-1个圆盘从auxPeg借助fromPeg移至toPeg towers(n-1,auxPeg,toPeg,fromPeg); }null*测试代码如下： #include   void main(void) { Towers(4, 'A', 'C', 'B'); } 程序运行的输出信息如下： null*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 Cnull*　　结合本节和6.2节的讨论，我们可总结如下：递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。 6.4递归过程和运行时栈*6.4递归过程和运行时栈 对于非递归函数，调用函数在调用被调用函数前，系统要保存以下两类信息： （1）调用函数的返回地址（从而能执行下一语句）； （2）调用函数的局部变量值。 当执行完被调用函数，返回调用函数前，系统首先要恢复调用函数的局部变量值，然后返回调用函数的返回地址。 　　递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在形式上类同，但保存信息的内容和方法不同。　　null*保存内容： 　 每一层递归调用所需要保存的信息构成一个工作记录，通常包括如下内容：     （1）本次递归调用中的局部变量值；     （2）返回地址，即本次递归过程调用语句的后继语句的地址；     （3）本次调用中与形参结合的实参值，包括函数名、引用参数与数值参数等。工作记录局部变量 返回地址 参 数null*保存方法:　　 递归函数被调用时，系统在运行递归函数前也要保存上述两类信息。但因为递归的函数的运行特点，是最后被调用的函数要最先被返回，若按非递归函数那样保存信息，显然要出错。 由于堆栈的后进先出特性正好与递归函数调用和返回的过程吻合，因此，高级程序设计语言利用堆栈保存递归函数调用的信息，系统用于保存递归函数调用信息的堆栈称为运行时栈。 运行时栈示意图栈顶栈底null* 递归函数被调用时，在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。 因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为活动记录。 工作记录活动记录运行时栈示意图栈顶栈底null我们以计算阶乘的递归函数为例，说明递归函数调用时运行时栈中工作记录的变化过程。*long Fact( int n) { int x; long y; If n == 0 return 1; else { x = n-1; y = Fact(x); return n * y; } }null 由于函数的地址是系统动态分配的，调用函数的返回地址因此也是动态变化的，不好给出具体数值，故下图中没有给出调用函数的返回地址。*运行时栈的变化过程long Fact( int n) { int x; long y; If n == 0 return 1; else { x = n-1; y = Fact(x); return n * y; } }6.5递归算法的效率分析*6.5递归算法的效率分析 我们先以斐波那契(Fibonacci)数列递归算法的执行效率为例来讨论递归算法的执行效率问题。 斐波那契数列Fib(n)的递推定义是： 如Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2, Fib(4)=3,Fib(5)=5,…,Fib(n)=null*求第n项斐波那契数列的递归函数过程如下： long Fib(int n) { if(n == 0 || n == 1) return n; //递归出口 else return Fib(n-1) + Fib(n-2); //递归调用 }null* 求Fib(5)的递归计算过程如图所示。 Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)斐波那契数列Fib(5)的递归调用树null* 为了计算Fib(5)，需要先计算Fib(4)和Fib(3)；而计算Fib(4)又需要计算Fib(3)（再一次计算）和Fib(2)，… … . 由上图可知，为了计算Fib(5)，需要计算1次Fib(4)，2次Fib(3)，3次Fib(2)，5次Fib(1)，3次Fib(0). 加上Fib(5)1次，所有的递归调用次数达到15次。（图中15个点表示15次运算） 更一般地，设Fib(n)需要总的递归调用次数为NumCall(n)，那么NumCall(n)等于多少？nullNumCall(n)= NumCall(n-1)+ NumCall(n-2)+1 NumCall(0)=1, NumCall(1)=1 可以求得NumCall的通项。也可以由下面的关系得到NumCall的通项。 NumCall(n) = 2*Fib(n+1) - 1。 可以证明，计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。*null计算斐波那契数列Fib(n)问题，我们也可根据公式写出循环方式求解的函数如下：*null*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; } }null* 上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为O(n)。对比循环结构的Fib2(n)和递归结构的Fib(n)可发现: 循环结构的Fib2(n)算法在计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列，因此其时间复杂度为O(n)； 而递归结构的Fib(n)算法在计算第n项的斐波那契数列时，必须首先计算第n-1项和第n-2项的斐波那契数列，而某次递归计算得出的斐波那契数列，如Fib(n-1)、Fib(n-2)等无法保存，下一次要用到时还需要重新递归计算，因此其时间复杂度为O(2n) 。 null下面我们再看看汉诺塔的时间复杂度。 设移动n个盘子的步数为H(n)，我们再看看示意图。*null*这一步实际有H(n-1)步这只需1步这一步又需要H(n-1)步故移动n个圆盘的总步数H(n)=H(n-1)+1+H(n-1) =2H(n-1)+1原柱 A 辅助柱 B 目标柱 C null即有 H(n)=2H(n-1)+1 S(1)=1 可以解得：H(n)=2n-1 因此汉诺塔的时间复杂度为O(2n) 。*6.6递归算法到非递归算法的转换*6.6递归算法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如下两种情况的递归算法。 （1）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。 （2）存在借助堆栈的循环结构的非递归算法，所有递归算法都可以借助堆栈转换成循环结构的非递归算法，如汉诺塔问题可以借助堆栈的循环结构实现非递归算法。null* 对于第一种情况，可以直接选用循环结构的算法。 对于第二种情况，可以把递归算法转换成相应的非递归算法，此时有两种转换方法：一种方法是借助堆栈，用非递归算法形式化模拟递归算法的执行过程；另一种方法是根据要求解问题的特点，设计借助堆栈的循环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。 通常，一个递归算法的模拟算法的复杂度与其本身的复杂度一样。null* 例6-6 借助堆栈模拟系统的运行时进栈、出栈过程，把汉诺塔问题的递归算法转化为非递归算法，并分析非递归算法的时间复杂度。6.7设计举例*6.7设计举例6.7.1 一般递归算法设计举例 例6-5 设计一个输出如下形式数值的递归算法。 n n n ... n ...... 3 3 3 2 2 1 null*问题分析：该问题可以看成由两部分组成：一部分是输出一行值为n的数值；另一部分是原问题的子问题，其参数为n-1。当参数减到0时不再输出任何数据值，因此递归的出口是当参数n≤0时空语句返回。 void Display(int n) { int i;  for(i = 1; i <= n; i++) cout< 0) Display(n - 1); //递归  //n<=0为递归出口，递归出口为空语句 }null*例6-6 设计求解委员会问题的算法。委员会问题是：从一个有n个人的团体中抽出k (k≤n)个人组成一个委员会，计算共有多少种构成方法。 问题分析：从n个人中抽出k(k≤n)个人的问题是一个组合问题。即求组合数公式C(n,k)。由于要所用递归算法,大家容易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k), 这个公式大家可以这样理解:把n个人固定位置后，从n个人中抽出k个人的问题可分解为两部分之和：第一部分是第一个人包括在k个人中，第二部分是第一个人不包括在k个人中。对于第一部分，则问题简化为从n-1个人中抽出k-1个人的问题；对于第二部分，则问题简化为从n-1个人中抽出k个人的问题。null* 当n=k或k=0时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的递推定义式为： 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); }null*例6-7 求两个正整数n和m最大公约数的递推定义式为： 要求： （1）编写求解该问题的递归算法； （2）分析当调用语句为Gcd(30, 4)时算法的执行过程和执行结果； （3）分析当调用语句为Gcd(5, 97)时算法的执行过程和执行结果； （4）编写求解该问题的循环结构算法。 null*解：（1）递归算法如下： 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); } null*（2）调用语句为Gcd(30, 4)时，因mn，递归调用Gcd(97, 5)；因m n) { tn = m; tm = n; } else { tn = n; tm = m; } While tm != 0 { temp = tn; tn = tm; tm = temp % tm;} return tn; }*null*6.7.2 回溯法及其设计举例 回溯法是递归算法的一种特殊形式，回溯法的基本思想是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。 null* 例6-10 设计求解迷宫问题的算法并用实际例子测试。