《数据结构》 第三章(下)
《 数据结构》 第三章（下）
数据结构 33栈与递归的实现 間鑫 个真接调用自己或通过一系列调用语句 地调用百己的函数称为递归函数。 A(){ B(){ C(){ A() C(); B(); A直接调用自己 B间接调用自己
数据结构 tjm A ( ) { … A( ) ; … } B( ) { C( ) { … … C( ); B( ); … … } } A 直接调用自己 B间接调用自己
数据结构 以下三种情况常常用到递归方法: 定义是递归的 数据结构是递归的 问题的解法是递归的 递归算法的编写: 1)将问题用递归的方式描述。 2)根据问题的递归描述编写递归算法 递归描述包括两项: 基本项(终止项):描述递归终止时问题的求解。 递归项:将问题分解为与原问题性质相同但规模较 小的问题
数据结构 tjm
数据结构 定义是递归的 【例1】阶乘函数 当n=0时 n米(n-1),当n≥1时 求解阶乘函数的递归算法: ong Factorial〔 long n) if (n ==0)return 1i else return n Factorial (n-1)i
数据结构 tjm 当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n
求解n!的过程 数据结构 参数 计算 返回 0 0!=1 1 0 参数 计算 返回 1* Factorial(o) 返 参数传递 参数 计算 返回 2 2* Factorial(1) 2 参数 计算 返回 3* Factorial(2) 6 6值 参数 计算 返回 壬* Factorial(3) 24 24 主程序main
数据结构 tjm
数据结构 【例2】计算斐波那契数列的函数Fib(n) n=0.1 Fib(n) Fib(n-1)+Fib(n-2), n>1 long Fib( long n) if(n<=1) return ni else return Fib(n-1)+ Fib(n-2);
数据结构 tjm ( 1) ( 2), 1 , 0,1 ( ) Fib n Fib n n n n Fib n
数据结构 数据结构是递归的 【例3】求数组A中n个整数的和 int sum( int n) if(n==1) result Aloi else result= A[n-1]+ sum(n-1); return result
数据结构 tjm
数据结构 【例4】单链表结构 f f 搜索链表最后一个结点并打印其数值 void Find( lnode f) if(f→next==NULL printf(%dⅦn",f→data) else Find( f -next);
数据结构 tjm
数据结构 问题的解法是递归的 【例5】汉诺塔问题 问题描述:有ABC三个塔座,A上套有n个直径 不同的圆盘,按直径从小到大叠放,形如宝塔编 号123…n。要求将n个圆盘从A移到C,叠 放顺序不变,移动过程中遵循下列原则: 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻,每个塔座上不能将大盘压到小盘上
数据结构 tjm
数据结构 解决方法: n=1时,直接把圆盘从A移到C。 n>1时,先把上面n-1个圆盘从A移到B然后将n号盘从A 移到C再将n-1个盘从B移到C。即把求解n个圆盘的 Hanoi问题转化为求解n-1个圆盘的Hano问题,依此类 推,直至转化成只有一个圆盘的Hano问题 B
数据结构 tjm