《数据结构》课程PPT教学课件（2015）第3章 栈和队列（下）

《数据结构》 第三章 栈和队列（下）

《 数据结构》 （下）

数据结构 3.3栈与递归的实现 高鑫地两角音整渴器鼠标努透站羲列调用语句 A(){ B(){ C(){ A(); C(): B(); A直接调用自己 B间接调用自己 tjm

数据结构 tjm A ( ) { . A( ) ; . } B( ) { C( ) { . . C( ); B( ); . . } } A 直接调用自己 B间接调用自己

数据结构 以下三种情况常常用到递归方法： 定义是递归的 数据结构是递归的 问题的解法是递归的 递归算法的编写： 1)将问题用递归的方式描述。 2)根据问题的递归描述编写递归算法。 递归描述包括两项： 基本项（终止项）：描述递归终止时问题的求解。 递归项：将问题分解为与原问题性质相同但规模较 小的问题

数据结构 tjm

数据结构 定义是递归的 【例1】阶乘函数 1, 当n=0时 n*(n-1)1,当n≥1时 求解阶乘函数的递归算法： long Factorial long n { if (n==0)return 1; else return n*Factorial(n-1) }

数据结构 tjm         当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n

求解n!的过程 数据结构 参数 计算 返回 0 01=1 1 参数 计算 返回 1*Factorial(0) 1 参 返 参数 计算 返回 数 2 2*Factorial(1) 2 2 回 传 参数 计算 返回 3 3*Factorial(2) 6 递 6 值 参数 计算 返回 4 4*Factorial(3) 24 24 主程序main

数据结构 tjm

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