清华大学：《数据结构》课程教学资源（PPT课件讲稿）第五章 递归

第沉章递归 递归( Recurve)的概念 迷宫(Maze问题 递归过程与递归工作栈 广义表( General lists)

递归(Recurve)的概念 迷宫(Maze)问题 递归过程与递归工作栈 广义表 (General Lists )

递归的概念 递归的定义若一个对象部分地包含它自 己,或用它自己给自己定义,则称这个对象 是递归的;若一个过程直接地或间接地调 用自己,则称这个过程是递归的过程 在以下三种情况下,常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的

递归的概念 递归的定义 若一个对象部分地包含它自 己, 或用它自己给自己定义, 则称这个对象 是递归的；若一个过程直接地或间接地调 用自己, 则称这个过程是递归的过程。 在以下三种情况下，常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的

定义是递的 例如,阶乘函数 当n=0时 n*(n-1)!,当n≥1时 求解阶乘函数的递归犷法 long Factorial (long n)& if(n==0)return 1; else return n* Factorial(n-1);

定义是递归的 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n*Factorial (n-1); } 例如，阶乘函数     −  = = 当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n

求解阶乘n!的过程 参数 计算 返回 0 0!=I 0 参数 计算 返回 1*Factorial(o) 参 1返 参数 计算 返回 数 2 2*Factorial(1) 2 传 参数 计算 返 3 Factorial (2) 6 递3 6值 参数 计算 返回 壬* Factorial(39) 24 24 主程序main

求解阶乘 n! 的过程

计算斐波那契数列的函数Fib(m)的定义 0.1 Fib(n) Fib(n-1)+Fib(n-2), n>1 求解斐波那契教列的递归犷法 long Fib( long n)& if (n<=1)return n; else return Fib(n-1)+ Fib(n-2);

计算斐波那契数列的函数Fib(n)的定义 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }    − + −  = = ( 1) ( 2), 1 , 0,1 ( ) Fib n Fib n n n n Fib n

数据结构是递归的 例如,单链表结构 f 搜索链表最后一个结点并打即其数值 template void Find( listNode sf)i if(f→link==NUL) cout≤<f→data<<endl; else find(f→lhik)

数据结构是递归的 搜索链表最后一个结点并打印其数值 template void Find ( ListNode *f ) { if ( f →link == NULL ) cout << f →data << endl; else Find ( f →link ); } 例如，单链表结构

在链表中寻找等于给定值的结点 并打印其数值 template void Print ListNode *)i if(f!= NULL) if(→dta==x) cout data < endl; else print(f→link);

在链表中寻找等于给定值的结点 并打印其数值 template void Print ( ListNode *f ) { if ( f != NULL) if ( f →data == x ) cout << f→data << endl; else Print ( f→link ); }

问题的解法是递归的 例如,汉诺塔( Tower of hanoi)问题 B

问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题

include #include strclass. h void Hanoi (int n, String A, string B, string C) {M解决汉诺塔问题的算法 if (n==1)cout <<"move <<a<< to <<C<< endl elsei Hanoi(n-1, A, C, B); cout <<move <<a<<to << c <K endl: Hanoi(n-1, B, A,C);

#include #include "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 ); } }

迷宫问题小型迷官「4 路口动作结果 76 3 1(入口)正向走进到2 23 左拐弯进到3 右拐弯进到4 4(堵死)回溯退到3 6 3(堵死)回溯退到2小左0直2右0 2正向走进到5型行3行5行6 迷 5(堵死)回溯退到2宫 2右拐弯进到6的 左拐弯进到7数 0007 0000 4000 (出口)据7

迷宫问题 小型迷宫 路口 动作 结果 1 (入口) 正向走 进到 2 2 左拐弯 进到 3 3 右拐弯 进到 4 4 (堵死) 回溯 退到 3 3 (堵死) 回溯 退到 2 2 正向走 进到 5 5 (堵死) 回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7 (出口) 4 3 5 2 1 7 6 6 左 0 直 2 右 0 行 3 行 5 行 6 0 0 4 0 0 0 0 0 0 7 0 0 7 小 型 迷 宫 的 数 据