数据结构 【例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