第6章 递归算法课件2.ppt

1、第第6章章 递归算法递归算法2main()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 136.4递归过程和运行时栈递归过程和运行时栈 对于非递归函数，调用函数在调用被调用函对于非递归函数，调用函数在调用被调用函数前，系统要保存以下两类信息：数前，系统要保存以下两类信息：（1 1）调用函数的返回地址（从而能执行下一）调用函数的返回地址（从而能执行下一语句）；语句）；（2 2）调用函数的局部变量值。）调用函数的局部变量值

2、。当执行完被调用函数，返回调用函数前，系当执行完被调用函数，返回调用函数前，系统首先要恢复调用函数的局部变量值，然后返回统首先要恢复调用函数的局部变量值，然后返回调用函数的返回地址。调用函数的返回地址。递归函数被调用时，系统要做的工作和非递递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在形式上类同，归函数被调用时系统要作的工作在形式上类同，但保存信息的内容和方法不同。但保存信息的内容和方法不同。4保存内容：保存内容：每一层递归调用所需要保存的信息构成一个工作记录，每一层递归调用所需要保存的信息构成一个工作记录，通常包括如下内容：通常包括如下内容：（1 1）本次递归调用中的局

3、部变量值；）本次递归调用中的局部变量值；（2 2）返回地址，即本次递归过程调用语句的后继语句）返回地址，即本次递归过程调用语句的后继语句的地址；的地址；（3 3）本次调用中与形参结合的实参值，包括函数名、）本次调用中与形参结合的实参值，包括函数名、引用参数与数值参数等。引用参数与数值参数等。5我们以计算阶乘的递归函数为例，说明递归函数调用我们以计算阶乘的递归函数为例，说明递归函数调用时运行时栈中工作记录的变化过程。时运行时栈中工作记录的变化过程。long Fact(int n)int x;long y;If n=0 return 1;else x=n-1;y=Fact(x);return n*

4、y;6 由于函数的地址是系统动态分配的，调用函数的返回地址因此也由于函数的地址是系统动态分配的，调用函数的返回地址因此也是动态变化的，不好给出具体数值，故下图中没有给出调用函数的是动态变化的，不好给出具体数值，故下图中没有给出调用函数的返回地址。返回地址。栈顶栈顶 3 2 1栈底栈底 0nxyFact初始时初始时运行时栈的变化过程 栈顶栈顶 321栈底栈底 03*nxyFact调用调用Fact(3)栈顶栈顶 3212*栈底栈底 032*nxyFact调用调用Fact(2)栈顶栈顶 321*121*栈底栈底 032*nxyFact调用调用Fact(1)栈顶栈顶 30*1210121*栈底栈底 0

5、32*nxyFact调用调用Fact(0)栈顶栈顶 321011121*栈底栈底 032*nxyFact返回返回Fact(0)栈顶栈顶 3212112栈底栈底 032*nxyFact返回返回Fact(1)栈顶栈顶 321栈底栈底 03226nxyFact返回返回Fact(2)栈顶栈顶 3 2 1栈底栈底 0nxyFact返回返回Fact(3)long Fact(int n)int x;long y;If n=0 return 1;else x=n-1;y=Fact(x);return n*y;76.6递归算法到非递归算法的转换递归算法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而

6、低级有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如需要采用问题的非递归结构算法。一般来说，存在如下两种情况的递归算法。下两种情况的递归算法。（1 1）存在不借助堆栈的循环结构的非递归算法，如）存在不借助堆栈的循环结构的非递归算法，如阶乘计算问题、斐波那契数列的计算问题、折半查找阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。问题等。（2 2）存在借助堆栈的循环结构的非递归算法，所有）存在借助堆栈的循环结构的非递归算法，所有递归算法都可以借助堆栈转换成循环

7、结构的非递归算递归算法都可以借助堆栈转换成循环结构的非递归算法，如汉诺塔问题可以借助堆栈的循环结构实现非递法，如汉诺塔问题可以借助堆栈的循环结构实现非递归算法。归算法。8 对于第一种情况，可以直接选用循环结构对于第一种情况，可以直接选用循环结构的算法。的算法。对于第二种情况，可以把递归算法转换成对于第二种情况，可以把递归算法转换成相应的非递归算法，此时有两种转换方法：一相应的非递归算法，此时有两种转换方法：一种方法是借助堆栈，用非递归算法形式化模拟种方法是借助堆栈，用非递归算法形式化模拟递归算法的执行过程；另一种方法是根据要求递归算法的执行过程；另一种方法是根据要求解问题的特点，设计借助堆栈的

8、循环结构算法。解问题的特点，设计借助堆栈的循环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻后进先出特点正好和递归函数的运行特点相吻合。合。通常，一个递归算法的模拟算法的复杂度通常，一个递归算法的模拟算法的复杂度与其本身的复杂度一样。与其本身的复杂度一样。96.7设计举例设计举例6.7.1 6.7.1 一般递归算法设计举例一般递归算法设计举例 例例6-5 6-5 设计一个输出如下形式数值的递归算法。设计一个输出如下形式数值的递归算法。n n n .nn n n .n.3 3 3 3 3 3 2 22 21 11

9、0问题分析：该问题可以看成由两部分组成：一部分是输出一行值为n的数值；另一部分是原问题的子问题，其参数为n-1。当参数减到0时不再输出任何数据值，因此递归的出口是当参数n0时空语句返回。void Display(int n)int i;for(i=1;i 0)Display(n-1);/递归 /n=0为递归出口，递归出口为空语句 11例例6-6 设计求解委员会问题的算法。委员会问题是：设计求解委员会问题的算法。委员会问题是：从一个有从一个有n个人的团体中抽出个人的团体中抽出k(kn)个人组成一个委个人组成一个委员会，计算共有多少种构成方法。员会，计算共有多少种构成方法。问题分析：从问题分析：从

10、n个人中抽出个人中抽出k(kn)个人的问题是一个个人的问题是一个组合问题。即求组合数公式组合问题。即求组合数公式C(n,k)。由于要所用递归。由于要所用递归算法算法,大家容易想到公式大家容易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),这个公式大家可以这样理解这个公式大家可以这样理解:把把n个人固定位置个人固定位置后，从后，从n个人中抽出个人中抽出k个人的问题可分解为两部分个人的问题可分解为两部分之和：第一部分是第一个人包括在之和：第一部分是第一个人包括在k个人中，第二个人中，第二部分是第一个人不包括在部分是第一个人不包括在k个人中。个人中。对于第一部分，则问题简化为从对于第

11、一部分，则问题简化为从n-1个人中抽个人中抽出出k-1个人的问题；对于第二部分，则问题简化为个人的问题；对于第二部分，则问题简化为从从n-1个人中抽出个人中抽出k个人的问题。个人的问题。13 当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是算，这是算法的递归出口。因此，委员会问题的递推定义式为：法的递归出口。因此，委员会问题的递推定义式为：int Comm(int n,int k)if(n 1|k n)return 0;if(k=0)return 1;if(n=k)return 1;return Comm(n-1,k-1)+Comm(n-1,k);其它时

12、当时当)1,-Comm(1)-1,-Comm(101),(Commknknknnkn15例例6-7 求两个正整数求两个正整数n和和m最大公约数的递推定义式为：最大公约数的递推定义式为：要求：要求：（1）编写求解该问题的递归算法；）编写求解该问题的递归算法；（2）分析当调用语句为）分析当调用语句为Gcd(30,4)时算法的执行过程和执时算法的执行过程和执行结果；行结果；（3）分析当调用语句为）分析当调用语句为Gcd(5,97)时算法的执行过程和执时算法的执行过程和执行结果；行结果；（4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。时当时当时当0)mod,(Gcd0),(Gcd)

13、,(Gcdmmnmmnmnnmmn16解：（1）递归算法如下：int Gcd(int n,int m)if(n 0|m n)return Gcd(m,n);else return Gcd(m,n%m);17（2）调用语句为Gcd(30,4)时，因mn，递归调用Gcd(4,2)；因mn，递归调用Gcd(97,5)；因mn，递归调用Gcd(5,2)；因mn，递归调用Gcd(2,1)；因mn，递归调用Gcd(1,0)；因m=0，到达递归出口，函数最终返回值为n=1，即5和97的最大公约数为1。18（4）循环结构算法循环结构算法int Gcd2(int n,int m)int tn,tm,temp;i

14、f(n 0|m n)tn=m;tm=n;else tn=n;tm=m;While tm!=0 temp=tn;tn=tm;tm=temp%tm;return tn;196.7.2 6.7.2 回溯法及其设计举例回溯法及其设计举例 回溯法是递归算法的一种特殊形式，回溯法的回溯法是递归算法的一种特殊形式，回溯法的基本思想是：对一个包括有很多结点，每个结点有基本思想是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜索

15、过程回溯退到该结点再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的前一结点，继续搜索这个结点的其他尚未搜索过的分支；如果发现这个结点也无法再继续搜索下去的分支；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的前时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。没有解存在为止。20 例6-10 设计求解迷宫问题的算法并用实际例子测试。算法如下：22 结构体如下：Typedef structint left;int forward;int right;InterSection;Typedef structint mazeSize;interSection*intSec;int Exit;6 0 2 0 3 5 6 0 0 4 0 0 0 0 0 0 7 0 0 723