文档介绍：数据结构
DATA STRUCTURE
第五章递归
第五章递归
递归与递归过程
递归的概念
递归过程
顺序搜索和二分搜索
顺序搜索
二分搜索
内容提要:
,理解递归的执行过程;
:顺序搜索和对半搜索。
递归的概念
一、递归的定义
递归是一个数学概念,递归函数即自调用函数,在函数体内直接或间接地自己调用自己。递归本质上也是一种循环的程序结构,它把“较复杂”的计算逐次归结为“较简单”的计算,一直归结到“最简单”的情形的计算,并得到计算结果为止。
二、用递归求解问题的条件
1. 必须有一个明确的函数终止的条件;
2. 原问题必须能转化为新问题,新问题的解决方法与旧问题的解决方法一样;
3. 新旧问题一般在形式参数每次获得的值上不一样,或者函数体内测试条件变量的值不同。
注意:很多数据结构可以采用递归方式定义,线性表、数组、字符串和树等数据结构原则上都可使用递归方法来定义。
使用递归定义方法的数据结构常称为递归数据结构,例如树形结构。
三、递归算法举例
例1:斐波那契级数
它的定义可递归定义如下:
F0=0
F1=1
Fn=Fn-1+Fn-2 (n>1)
其递归算法如下:
long Fib(long n)
{
if (n<=1) return n;
else return Fib(n-2)+Fib(n-1)
}
说明:
,当n>1时,又调用了函数Fib自己,但是形式参数变为当前参数值n的减2和减1,新问题的解决与原问题的解决方法一样,但新问题的解决比原问题更趋向于简单,因为形式参数在减小。当形式参数n<=1时,递归将终止,返回当前n的值。
:
(1)直接递归方式:P->P,即在函数P的函数体内有语句直接调用函数P。
以上的Fib函数就是一个直接递归函数
(2)间接递归方式:P->Q->P,即在函数P的函数体内有语句调用函数Q,而在函数Q的函数体内又有语句调用函数P,这样考察函数P,就是通过函数Q间接地调用自己,这就是间接递归方式,本章不考虑此类递归。
递归过程
一、递归算法的优点
程序非常简洁而清晰,并且易于分析,可读性较强。
二、递归算法的缺点
(1)费空间:系统实现递归需要一个系统栈,用于在程序运行时间处理函数调用。系统栈是一块特殊的存储区。当一个函数被调用时,系统创建一个工作记录,称为栈桢(stack frame),并将其置于栈顶。初始时只包括返回地址和指向上一栈的指针。当该函数调用另一个函数时,该函数的局部变量、参数将加到它的栈桢中。一旦一个函数运行结束,将从栈中删除它的栈桢,程序控制返回原调用函数继续执行下去。
例如:main() 函数调用函数a1,图5-1(a)表明了main()函数系统栈,而图5-1(b)是包括函数a1的系统栈。
局部变量参数
上一帧指针
返回地址
局部变量参数
上一帧指针
返回地址
局部变量参数
上一帧指针
返回地址
fp
main
fp
a1
(a) main函数
(b) a1函数
图5-1 系统栈示意图
(2) 费时:局部变量、形式参数和返回地址的进栈、出栈以及参数的传递需要费时,而且递归中的重复计算也很浪费时间。
例:当调用Fib(4)时,由下图所示的递归树可以看出,递归调用期间发生了很多次重复计算,因而费时。
Fib(4)
Fib(2) Fib(3)
Fib(0) Fib(1) Fib(1) Fib(2)
Fib(0) Fib(1)
图5-2 Fib(4)的递归树
三、递归算法可用等效非递归算法实现
因为递归费时费空间,如果可能,一般将递归改为非递归。递归的递和归的过程实际上实现了一个循环结构,因此有些问题直接用循环的非递归函数来解决。
例:输出数组元素的递归和非递归函数
void rsum(int list[],int n) void rsum(int list[],int n)
{ if (n>=0) { { while (n>=0) {
cout<<list[n]<<““; cout<<list[n]<<““;
rsum(list ,--n);} --n;}
} }
需要说明的是:实际上所有的递归算法都可用等效的非递归算法来实现,但有时出于可读性和编程简单性方面的考虑,有些算法仍用递归实现较好。