第六章 递归算法.ppt

第6章 递归算 法 情景 小时候，我们听过这样的故事： 从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的是什么故事呢？从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的是什么故事呢？从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的是什么故事呢？…… 故事可以一直讲下去，每一个故事内容相同，单却是故事里的故事。 这就是现实里的递归！ 选取数组的下标为low，上标为high，数组的中间位置下标mid=（low+high）/2； 如果x=a[mid]，则查找成功； 如果xa[mid]，则low=low，high=mid-1； 如果xa[mid]，则low=mid+1，high=high； int f( int x) int f1( int x) int f2( int x) { int y, z； { int y, z； { int a,c； ┇ ┇ ┇ z＝f(y)； z＝f2(y)； c＝f1(a)； ┇ ┇ ┇ return(2*z); return(2*z); return(3+c); ｝ ｝ ｝ (a) (b) 例如，要想将A柱上3个盘子移到C柱上，可以分解为以下三步： 1. 将A上2个盘子从A移到B（借助C）。 2. 将A上1个盘子从A移到C。 3. 将B上2个盘子从B移到C（借助A）。 其中第2步可以直接实现。第1步又可用递归方法分解为： 2.1 将A上1个盘子从A移到C。 2.2 将A上1个盘子从A移到B。 2.3 将C上1个盘子从C移到B。 第3步可以分解为： 3.1 将B上1个盘子从B移到A上。 3.2 将B上1个盘子从B移到C上。 3.3 将A上1个盘子从A移到C上。 上面第1步和第3步，都是把n-1个盘从一个柱移到另一个柱上，采取的办法是一样的，只是柱的名字不同而已。 写出程序输出结果 #includestdio.h int f(int a,int b,int n) { if(n==1) return a; if(n==1) return b; return f(b,a+b,n-1); } void main(){printf(%d,f(1,1,7));} void delete(LinkList L, ElemType x) { // 删除以L为头指针的带头结点的单链表中 // 所有值为x的数据元素 if (L-next) { if (L-next-data==x) { p=L-next; L-next=p-next; free(p); delete(L, x); } else delete(L-next, x); } } // delete 6.4 递归过程和运行时栈 　 对于非递归函数，调用函数在调用被调用函数前，系统要保存以下两类信息： （1）调用函数的返回地址； （2）调用函数的局部变量值。 　 当执行完被调用函数，返回调用函数前，系统首先要恢复调用函数的局部变量值，然后返回调用函数的返回地址。 　　递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在形式上类同，但保存信息的方法不同。 　　递归函数被调用时，系统的运行时栈也要保存上述两类信息。 每一层递归调用所需保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶。 每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为活动记录。 6.5 递归算法的效率分析 斐波