数据结构 递归

数据结构递归第一页，共二十九页，2022年，8月28日

栈和递归在程序设计中的应用是非常广泛的，如对于迷宫的求解、表达式的求解等都可以用栈来解决。典型的hanoi塔问题，树和图的遍历等都可以用递归来解决。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，递归算法简明易懂。第二页，共二十九页，2022年，8月28日6.1递归的定义什么是递归

xn=x*x*…*x*x（n个x连乘）

xn+1=xn*xS(n)=1+2+3+…+(n-1)+n

S(n+1)=S(n)+(n+1)

优点：直观、有效第三页，共二十九页，2022年，8月28日定义：如果一个对象部分地包含它自身，或者利用自己定义自己的方式来定义或描述，则称这个对象是递归的；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程。直接调用自身的递归过程称为直接递归。调用另一个过程并最终导致调用原过程的递归过程称为间接递归组成：递归调用、递归终止条件第四页，共二十九页，2022年，8月28日5第五页，共二十九页，2022年，8月28日递归求解的过程：对于一个比较复杂的问题，若能将它分解成若干相对简单、且解法相同或类似的子问题，那么当这些子问题获解时，原问题就获得求解－－分治策略。子问题无需分解就可直接求解时，停止分解，直接求解该子问题－－递归结束条件。7第六页，共二十九页，2022年，8月28日求解阶乘函数的递归过程longFactorial(longn){ if(n==0)return1;//递归终止条件

else returnn*Factorial(n-1);}

//递归调用过程第七页，共二十九页，2022年，8月28日以下三种情况适于用递归求解问题：问题的定义是递归的问题所涉及的数据结构是递归的；问题的解法满足递归的性质。第八页，共二十九页，2022年，8月28日1、问题的定义是递归的阶乘函数、幂函数和斐波那契数列。[例]阶乘函数的定义用(n-1)!定义n!第九页，共二十九页，2022年，8月28日计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(

longn){

if(n<=1)

returnn;

elsereturnFib(n-1)+Fib(n-2);}

第十页，共二十九页，2022年，8月28日2、问题所涉及的数据结构是递归的[例]单链表head=NULL●head指向一个空结点的数据结构是一个单链表。●head指向一个非空结点，该结点的指针域指向一个单链表，这样的数据结构是一个单链表。7245…head36∧第十一页，共二十九页，2022年，8月28日二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子树）构成。 第十二页，共二十九页，2022年，8月28日3、问题的解法满足递归的性质例如，汉诺塔(TowerofHanoi)问题问题的提出：在19世纪末，布拉玛神庙(TempleofBramah)里的传教士玩着一种游戏，据说他们的游戏装置是由一块铜板上有三根金刚石针，针上放有64个直径大小不等的金盘组成的。游戏的目标是把左面针上的金盘移动到右面的针上，移动过程中一次只能移动一个盘子，不允许大盘放在小盘上面，只能借助于中间的针。他们认为这种游戏的结束就意味着世界末日的到来。欧洲人把这种游戏叫做汉诺塔(TowerofHanoi)游戏。第十三页，共二十九页，2022年，8月28日第十四页，共二十九页，2022年，8月28日第十五页，共二十九页，2022年，8月28日第十六页，共二十九页，2022年，8月28日6.2基本递归过程递归过程在实现时，发生递归调用：分为内部调用和外部调用。

函数调用与过程调用递归调用正确进行：调用时参数传递正确过程结束正确返回：返回地址正确第十七页，共二十九页，2022年，8月28日在高级语言（编译程序）中，是利用“递归工作栈”来实现递归调用的。

f(n)f(n-1)f(n-2)f(1)f(0)调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场。…调用返回调用点

PnPn-1Pn-2P11第十八页，共二十九页，2022年，8月28日层层向下递归，退出时的次序正好相反：递归次序

n!(n-1)!(n-2)!1!

0!=1

返回次序工作记录：

返回地址 参数（函数名、引用参数与数组参数等）局部变量第十九页，共二十九页，2022年，8月28日函数递归时的活动记录第二十页，共二十九页，2022年，8月28日

“当前活动工作记录”

递归工作栈

局部变量返回地址参数……局部变量返回地址参数第二十一页，共二十九页，2022年，8月28日程序运行期间一个函数调用另一个函数之前需作三件事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转以移到被调函数的入口。从被调函数返回调用函数之前需作三件事：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转移到调用函数。；第二十二页，共二十九页，2022年，8月28日注意：（1）有递归函数调用时进栈；（2）递归函数结束时，若栈不空则出栈；（3）递归函数结束时，栈空程序结束。；第二十三页，共二十九页，2022年，8月28日

longFactorial(

longn){if(n==0)return1;elsereturnn*Factorial(n-1);//函数调用L1: }

voidmain(){

intResult;

Result=Factorial(4);L0: }

函数调用举例

第二十四页，共二十九页，2022年，8月28日计算Factorial时活动记录的内容

栈底

第二十五页，共二十九页，2022年，8月28日过程调用举例//中序遍历以t为根的子树,C++实现voidBinTree<T>::InOrder(BinTreeNode<T>*t){if(t!=NULL){

InOrder(t→left);//过程调用cout<<t→data;

InOrder(t→right);}}

第二十六页，共二十九页，2022年，8月28日6.3

递归的效率递归技术的运用，是在牺牲计算机内存空间的基础上得到的。当一个问题蕴含着递归关系且结构比较复杂时，采用一般的算法，不仅给程序的设计带来许多困难，而且也会给设计出的程序带来篇幅大、可读性差的缺点，这时采用递归技术来设计程序则会带来很好的效果。第二十七页，共二十九页，2022年，8月28日

递归的优点和缺点优点：递归函数结构