递归教学课件

第5章递归（Recurve）

定义:若一个对象部分地包含它自己，或用它自己给自己定义，则

称这个对象是递归的；而且一个过程直接地或间接地调用自

己，则称这个过程是递归的过程。

应用：

(1)用于某些概念的定义：

阶乘：if(n>0)n!=n(n-1)!

if(n=0)n!=1

单链表结点：

template<classType>classListNode

{private:

Typedata;

ListNode<Type>*Link;

二叉树：二叉树是数据元素的有穷集合，它或者为空集（空

二叉树），或者由一个根元素和其下的两棵互不相

交的二叉树（左子树和右子树）构成。

2011-6-30

(2)用于编程

longf(longn)

〃求自然数n的阶乘n!,n>=0

{if(n=0)return1;

elsereturnn*f(n-1);

)

递归算法的优点：易编程、可读性好、易检验

可用归纳思维方法来理解和检验递归算法，但有一个基本条件

和两个步骤：

基本条件：规格说明必须严格、精确地规定算法的功能、

入/出口信息、对外层量或全局量的影响

步骤一：归纳基始——验证算法对于最简单情况(递归出

口)的正确性

步骤二：由归纳假设进行归纳——假设算法中的递归调用

能正确实现规格说明之规定，然后验证整个算法

能否实现规格说明之规定

2011-6-302

递归算法举例——迷宫问题递归算法

voidRecurveSeek(inti,j)

〃进入时(i,j)是一通道块，尚未印足迹，不在当前路径上。本函数

〃从(i,j)起探索并输出以此时当前路径为前缀的所有成功的简单路

〃径，退出时状态同进入时状态

{maze[i][j]=U;〃印足迹，归入当前路径

if(i==n&&j=n)printmaze();〃简单情况

elsefbr(k=0;kv4;k++)//试探东南西北四个方向

if(maze[i+di[k]][j+dj[k]]==66)〃若下一块是通道

RecurveSeek(i+di[k],j+dj[k]);〃则递归调用

maze[i,j]=—;〃回溯，恢复进入时状态

假定入口为(0,0),则只需执行下列函数调用即可找到迷宫的

所有简单路径：

RecurveSeek(0,0);

2011-6-303

5.3递归过程与递归工作栈

为了保证递归调用的正确性，需要保存调用点的现场(返回地

址、局部变量、被调用函数的参数等)，以便正确地返回，并且按

先进后出的原则来管理这些信息。在高级语言(编译程序)中，是

通过利用“递归工作栈”来实现递归调用的。

f(n)f(n-l)f(n-2)f(l)f(0)

调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场

2011-6-304

计算4!递归过程图示：

下图中Pi代表现场信息，栈元素由现场信息和参数构成

共4尸4**3)一*3尸3**2)—＞我2尸2*瑁)一"f(l)=l*f(O)一氏0尸1

Push(e4)Push(e3)Push(e2)Push(el)

p

Pop(e2)

P22P22

卜

P332P33P33

P44P44

Pop(e4)

f(4)=4*.3).-----.)=3*氏2)一出2尸2*f(l)-f(l)=1*f(0)

一般来说，递归方法的执行效率较低，但编程效率较高，因此

常用来构建快速原型。另外递归结构一般可以转化成循环结构(有

时需要栈操作的配合)。试实现上述阶乘计算的转化(要求用栈)。

2011-6-305

2011-6-306

2011-6-307

SuccesswithMoneyandJoy

附落人生心语

•成功是一种观念

•致富是一种义务

•快乐是一种权利

•每个人都有能力、有义

务、有权利办到成功

致富快乐

附赠人生心语

成成功不是打败别人

功成功不是超越别人

成功不是名、利、权的获得

致拥有健康的身体

丰足的物质生活

富平衡的心理状态

又才能拥有成功

快SuccesswithMoneyandJoy

战胜自己

乐贡献自己

扮演好自己的历史角色

才能超越自己

融入成功里

附赠人生心语

知人者智，自知者明，胜人者力，自

胜者强。

——老子

附赠人生心语

•成功必须靠百分之九十八的辛勤血

汗，加上百分之二的天才灵感。

•世界上注定只有百分之二十的人会成

功。

附赠人生心语

成犹太谚语中有一句名言，

功会伤人的东西有三个：苦恼、争吵、空的钱包。

其中最伤人的是——空的钱包。

致金钱本身并没有善恶，

但没有钱，

富却的确是一件不幸的事情。

又所以，我们必须学习

快SuccesswithMoneyandJoy

重视财富，

乐管理财富，

更重要的是栗学会

正确地

使用自己的财富。

附赠人生心语

重财---重视自己的财富

孔子说：“不义而富且贵于我如浮云。”只要

是正正当当的钱，都应该被珍惜、被重视。

附赠人生心语

理财-----管理自己的财富

在贫苦和缺钱里挣扎的人，都有一个共同的特

点，就是不会理财，甚至不懂什么是理财。

附磨人生心语

增贝才----增加自己的财富

劳务收入

收入卜

财务收入

附霜人生心语

守贝才-----保护自己的财富

守财三原则：

・不赌钱

・不借钱

•不投资做生意

附赠人生心语

成

功春有百花秋有月，夏有凉风冬有雪

致若无闲事挂心头，便是人间好时节

富

又SuccesswithMoneyandJoy

快快乐是一种角度

由反面看可能是苦，由正面看可能是乐

乐快乐是一项权利，没有人能限制