递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.ppt
《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.ppt》由会员分享,可在线阅读,更多相关《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.ppt(61页珍藏版)》请在三一文库上搜索。
1、递归的概念 递归过程与递归工作栈 递归与回溯 广义表,第五章 递归与广义表,递归的概念,递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,定义是递归的,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); ,例如,阶乘函数,求解阶乘 n! 的过程,主程序 main : fact(
2、4),参数 4 计算 4*fact(3) 返回 24,参数 3 计算 3*fact(2) 返回 6,参数 2 计算 2*fact(1) 返回 2,参数 1 计算 1*fact(0) 返回 1,参数 0 直接定值 = 1 返回 1,参数传递,结果返回,递归调用,回归求值,数据结构是递归的,一个结点,它的指针域为NULL,是一个单链表; 一个结点,它的指针域指向单链表,仍是一个单链表。,例如,单链表结构,f,f,搜索链表最后一个结点并打印其数值 template void Print ( ListNode *f ) if ( f -link = NULL ) cout data link ); ,
3、f,f,f,f,f,a0,a1,a2,a3,a4,递归找链尾,在链表中寻找等于给定值的结点并打印其数值 template void Print ( ListNode *f, Type ,f,f,f,f,递归找含x值的结点,x,问题的解法是递归的 例如,汉诺塔(Tower of Hanoi)问题的解法: 如果 n = 1,则将这一个盘子直接从 A 柱移到 C 柱上。否则,执行以下三步: 用 C 柱做过渡,将 A 柱上的 (n-1) 个盘子移 到 B 柱上: 将 A 柱上最后一个盘子直接移到 C 柱上; 用 A 柱做过渡,将 B 柱上的 (n-1) 个盘子移 到 C 柱上。,#include #i
4、nclude “strclass.h” void Hanoi (int n, String A, String B, String C) /解决汉诺塔问题的算法 if ( n = 1 ) cout “ move “ A “ to “ C endl; else Hanoi ( n-1, A, C, B ); cout “ move “ A “ to “ C endl; Hanoi ( n-1, B, A, C ); ,递归过程与递归工作栈,递归过程在实现时,需要自己调用自己。 层层向下递归,退出时的次序正好相反: 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次
5、调用递归过程为外部调用; 递归过程每次递归调用自己为内部调用。 它们返回调用它的过程的地址不同。,递归工作栈,每一次递归调用时,需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录,按后进先出的栈组织。,局部变量 返回地址 参 数,活动记录框架,递归 工作记录,函数递归时的活动记录,. ,Function() . ,调用块,函数块,返回地址(下一条指令) 局部变量 参数,long Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1);
6、RetLoc2 return temp; ,void main ( ) int n; n = Factorial (4); RetLoc1 ,计算Fact时活动记录的内容,递归调用序列,0 RetLoc2,1 RetLoc2,2 RetLoc2,3 RetLoc2,4 RetLoc1,参数 返回地址 返回时的指令,RetLoc1 return 4*6 /返回24,RetLoc2 return 3*2 /返回6,RetLoc2 return 1 /返回1,RetLoc2 return 1*1 /返回1,RetLoc2 return 2*1 /返回2,递归过程改为非递归过程,递归过程简洁、易编、易
7、懂 递归过程效率低,重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); ,如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5,调用次数 NumCall(k) = 2*Fib(k+1) - 1,斐波那契数列的递归调用树,Fib(1),Fib(0),Fib(1
8、),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(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),栈结点,n tag,tag = 1, 向左递归;tag = 2, 向右递归,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 3 1 4 1,n=1 sum=0+1,2 2 3 1 4 1,n=2-2,3 1 4 1,
9、n=0 sum=1+0,3 2 4 1,n=3-2,4 1,n=1 sum=1+1,4 2,n=4-2,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 1 4 2,n=1 sum=2+1,2 2 4 2,n=2-2,4 2,n=0 sum=3+0,long Fibnacci ( long n ) Stack S; Node *w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w-n = n; w-tag = 1; S.push ( w ); n-; /向左递
10、归到底, 边走边进栈 sum = sum + n; /执行求和,while ( !S.IsEmpty( ) ) w = S.getTop( ); S.Pop( ); if ( w-tag = 1 ) /改为向右递归 w-tag = 2; S.push ( w ); n = w-n 2; /F(n)右侧为F(n-2) break; while ( !S.IsEmpty( ) ); return sum; ,单向递归用迭代法实现,long FibIter ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current
11、; for ( int i = 2; i = n; i+ ) Current = twoback + oneback; twoback = oneback; oneback = Current; return Current; ,void recfunc ( int A , int n ) if ( n = 0 ) cout An “ ”; n-; recfunc ( A, n ); ,25 36 72 18 99 49 54 63,尾递归用迭代法实现,void sterfunc ( int A , int n ) /消除了尾递归的非递归函数 while ( n = 0 ) cout “val
12、ue “ An endl; n-; ,递归与回溯 常用于搜索过程,n皇后问题 在 n 行 n 列的国际象棋棋盘上,若两个皇后位于同一行、同一列、同一对角线上,则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。,1#主对角线 3#主对角线 5#主对角线,0#次对角线 2#次对角线 4#次对角线 6#次对角线,1#次对角线 3#次对角线 5#次对角线,0#主对角线 2#主对角线 4#主对角线 6#主对角线,0 1 2 3,0 1 2 3,k = i+j,k = n+i-j-1,解题思路,安放第 i 行皇后时,需要在列的方向从 0 到 n-1 试探 ( j = 0, , n-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 概念 过程 工作 回溯 广义 ppt 课件
链接地址:https://www.31doc.com/p-2578711.html