文档介绍：递归的概念
递归过程与递归工作栈
递归与回溯
广义表
第五章 递归与广义表
编辑课件
递归的概念
递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己需分配的空间形成递归工作记录，按后进先出的栈组织。
局部变量
返回地址
参 数
活动记录框架
递归
工作记录
编辑课件
函数递归时的活动记录
……………….
<下一条指令>
Function(<参数表>)
……………….
<return>
调用块
函数块
返回地址(下一条指令) 局部变量 参数
编辑课件
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2
return temp;
}
void main ( ) {
int n;
n = Factorial (4);
RetLoc1
}
编辑课件
计算Fact时活动记录的内容
递归调用序列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
RetLoc1 return 4*6 //返回24
RetLoc2 return 3*2 //返回6
RetLoc2 return 1 //返回1
RetLoc2 return 1*1 //返回1
RetLoc2 return 2*1 //返回2
编辑课件
递归过程改为非递归过程
递归过程简洁、易编、易懂
递归过程效率低，重复计算多
改为非递归过程的目的是提高效率
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程
编辑课件
计算斐波那契数列的函数Fib(n)的定义
求解斐波那契数列的递归算法
long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2);
}
如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5
编辑课件
调用次数 NumCall(k) = 2*Fib(k+1) - 1
斐波那契数列的递归调用树
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(3)
Fib(4)
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(3)
Fib(5)
编辑课件
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
栈结点
n tag
tag = 1, 向左递归；tag = 2, 向右递归
编辑课件
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2
4 1
n=1
sum=1+1
4 2
n=4-2
编辑课件
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0