11.1 递归的定义 11.2 常见递归问题 11.3 递归的实现 11.4 递归转化为非递归的一般过程 11.5 递归的时间和空间复杂度

Presentation on theme: "11.1 递归的定义 11.2 常见递归问题 11.3 递归的实现 11.4 递归转化为非递归的一般过程 11.5 递归的时间和空间复杂度"— Presentation transcript:

1 11.1 递归的定义 11.2 常见递归问题 11.3 递归的实现 11.4 递归转化为非递归的一般过程 11.5 递归的时间和空间复杂度
第十一章 递归 11.1 递归的定义 11.2 常见递归问题 11.3 递归的实现 11.4 递归转化为非递归的一般过程 11.5 递归的时间和空间复杂度

2 11.1 递归的定义 概念： 递归：一个事件或对象部分的由自己组成，或者按它自己来定义 递归算法分为递推和回归
11.1 递归的定义 概念： 递归：一个事件或对象部分的由自己组成，或者按它自己来定义 递归算法分为递推和回归 递推： 为得到问题的解，将其推到比原来问题简单的问题求解上 回归 ：简单问题得到解后，回归到原问题的解上

3 间接递归：一函数在调用其他函数时，又产生了对自身的调用 A( ) B( )
递归函数分类： 直接递归：函数直接调用本身 A( ) {…… CALL A( ) ...... } 间接递归：一函数在调用其他函数时，又产生了对自身的调用 A( ) B( ) {…… {…… CALL B（） CALL A（） …… } …… }

4 11.2 常见递归问题 汉诺塔问题 八皇后问题 组合公式的计算

5 汉诺塔问题 问题描述：有三个命名为A、B、C的塔座，在塔座A上插有n个直径各不相同的，从小到大依次编号为1，2，3，……，n的圆盘，编号越大的圆盘其直径越大；要求将A轴上的n个圆盘全部移至塔座C上并仍按同样顺序叠放，并且圆盘移动时必须遵循下列规则： 每次只能移动一个圆盘； 圆盘可以插入A、B、C中任一个塔座上； 任何时候都不能将一个较大的圆盘压在较小的圆盘上

6 事例：n=3

7 事例：n=6

8 算法： void hanoi ( int n, char x, char y, char z) {/*递归算法*/
if(n= =1) move（x，z）； else { hanoi（n-1，x，z，y）；/*把N-1个盘子从X借助Z移到Y*/ printf（”%c-%c\n”, x，z）；/*把盘子N从X直接移到Z*/ hanoi（n-1，y，x，z）；/*把N-1个盘子从Y借助X移到Z */ }

9 八皇后问题 问题描述：在一个88的棋盘上放置8个皇后，那么n个皇后的问题就是在nn的棋盘上放置n个皇后；规则是：不允许两个皇后在同一行，同一列或同一对角线上 图示：

10 事例：四皇后问题：

11 算法： Void Eight_que(int q) { int i,j; while(i<max_N) {
if (search(q,i)！= null) queen[q]=j; if(q=max_n-1) for(j=1;j<max_n;j++) printf(“%d,%d”,j, queen (j)); } else Eight_que(q+1); i++; } }

12 int search(int x,int i) { int j,m,atk; atk=0; j=1; while(atk = =0) && (j < x)) m= queen[j]; atk=(m= =i)||(abs(m-i)= = abs(j-x)); j++; } return(atk); }/*search*/

13 组合公式的计算 问题描述：

14 11.3 递归的实现 采用递归算法具备的条件 递归的实现机制 要解决的问题可以转化成另一个问题，解决新问题的方法与原始问题的解决方法相同
11.3 递归的实现 采用递归算法具备的条件 要解决的问题可以转化成另一个问题，解决新问题的方法与原始问题的解决方法相同 必须具备终止递归的条件 递归的实现机制 分配调用过程函数所需要的数据区 保存返回地址，传递参数信息 把控制权转移给被调用函数

15 被调用函数运行结束，需完成： 递归工作栈 的变化： 保存返回时的有关信息 释放被调有函数占用的数据区
按调用时保存的返回地址，把控制权转移到调用函数中调用语句的下一条语句 递归工作栈 的变化：

16 事例一：求n！ 算法： int Dg( int n) { long y； int x； x=n-1； if (n<0)
return error； else if ( n = =0|| n = =1 ) return(1)； y= Dg(x) return(Dg(x) * n)； }

17 事例二：调用dg（n），求6！

18 事例三：斐波那齐数列（Fibonacci Number） fib(n)= 算法：
int fib（int n） { if（n<=1） return（ n）； Else return（fib（n-1）+fib（n-2））； } n n=0或n=1 fib(n-1)+fib(n-2) n>1

19 求fib(6)

20 11.4 递归转化为非递归的一般过程 转换步骤： 转换算法： #define max 50 typedef struct {
11.4 递归转化为非递归的一般过程 转换步骤： 写出问题的递归形式 转换成模拟形态，包括准备所有栈和临时地址 除去多余的栈和变量 得到一有效的非递归程序 转换算法： #define max 50 typedef struct { int param； int x； long y； short return_addr；/*返回地址*/ }elemtype；

21 typedef struct { int top； elemtype item（max）； }qstype； #include <stdio.h> #include stack.h long simfact（int n） { elemtype curr_area； /*当前工作区的指针*/ qtype s； /*栈数据区的指针*/ long result； /*传递当前执行的结果*/ short i； /*判断转向的返回地址*/ s．Top=-1； curr_area.x=0; curr_area.y=0; curr_area.Param=0; curr_area.return_addr=0; pushQ(&s,curr_area); curr_area.Param=0;

22 curr_area.return_addr=1;/*返回地址1*/
while(!Empty(s)) { if (curr_area.Param= =0) result=1; i= curr_area.return_addr;/*取当前返回地址*/ Curr_area=PopQ(&s);/*退栈*/ Switch(i) case 1: goto addr_1; case 2: goto addr_2; } curr_area.x=curr_area.Param-1; PushQ(&s, (curr_area); Curr_area.Param=curr_area.x; Curr_area.return_addr=2;/*返回地址2*/

23 addr_2: /*以下模拟返回递归调用(即返回地址2)过程*/ curr_area.y = result; result=(curr_area.Param)*(curr_area.y); i= curr_area.return_addr; Curr_area=popQ(&s); Switch(i) { case 1: goto addr_1; case 2: goto addr_2; } /*以下模拟返回主调用函数(即返回地址1)过程*/ addr_1: return(result);

24 事例：斐波那齐数列的非递归算法 void fib（int n） { int prev，now，next，j；
if（n<=1）return(n); else prev=0; now=1; for(j=2;j<=n;j++) next=prev+now; prev=now; now=next; } return(next);

25 11.5 递归的时间和空间复杂度 事例讨论：非递归的实现6！的算法 时间复杂度为：T（6）=O（1） 空间空间复杂度：O（1）
11.5 递归的时间和空间复杂度 事例讨论：非递归的实现6！的算法 Int Dg( ) { int i, result; result=1; for (i= =1; i<6; i++) result=result*i; return result; } 时间复杂度为：T（6）=O（1） 空间空间复杂度：O（1）

26 时间复杂度：T（6）=O(f1(6))+O(f2(6)) 空间复杂度比非递归的要大
6！递归实现的算法 int Dg(n) {/*递归调用函数*/ int f； if (n<0) return error； else if (n= =0|| n= =1) f=1； f=dg(n-1)*n； return(f )； } 时间复杂度：T（6）=O(f1(6))+O(f2(6)) 空间复杂度比非递归的要大