数据结构 【例2】计算斐波那契数列的函数Fib(n) n, n=0,1 Fi6(0）=Fi(n-)+Fib(n-2 ,n>1 long Fib long n) { if(n<=1) return n; else return Fib(n-1)+Fib(n-2)i } tjm
数据结构 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 A[O]; else result A[n-1]sum(n-1) return result;
数据结构 tjm
数据结构 【例4】单链表结构 搜索链表最后一个结点并打印其数值 void Find LNode *f { if f-next =NULL printf("%d \n",f-data ) else Find(f→next)i
数据结构 tjm
数据结构 问题的解法是递归的 【例5】汉诺塔问题 问题描述：有A,B,C三个塔座，A上套有n个直径 不同的圆盘，按直径从小到大叠放，形如宝塔编 号1,2,3.n。要求将n个圆盘从A移到C,叠 放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上
数据结构 tjm
数据结构 解决方法： n=1时，直接把圆盘从A移到C。 n>1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A 移到C,再将n-1个盘从B移到C。即把求解n个圆盘的 Hanoil问题转化为求解n-1个圆盘的Hanoil问题，依此类 推，直至转化成只有一个圆盘的Hanoil问题
数据结构 tjm