递归Pascal-递归递归的概念.ppt

文档介绍：第七讲　递归
递归Pascal-递归递归的概念
一、递归的概念
若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。
递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。
n!=n*(n-1)!
F(n)=F(n-1)+F(n-2)
递归Pascal-递归递归的概念
一、递归的概念
对于一个递归定义而已，除了要定义递归的方式（即如何递归）外，还必须定义递归的终止条件（即如何停止递归），否则递归将永无止境的进行下去。
递归Pascal-递归递归的概念
程序一般调用
子程序 A
调用 A
主程序
子程序 A
子程序 B
调用 B
主程序
主程序
子程序 A
子程序 B　……　调用 A　……
递归Pascal-递归递归的概念
程序递归调用
主程序
子程序 A　……　调用 A　……
主程序
子程序 A
子程序 B　……　调用 A　……
主程序
子程序 A　……　调用 B　……
子程序 B　……　调用 A　……
递归Pascal-递归递归的概念
Pascal语言中的向前引用
procedure b; forward;
procedure a;
begin
b;
end;
procedure b;
begin
a;
end;
递归Pascal-递归递归的概念
二、递归算法用于解决的问题
一般来说，能够用递归解决的问题应该满足以下三个条件：
需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同；
递归调用的次数必须是有限的；
必须有结束递归的条件（边界条件）来终止递归。
递归Pascal-递归递归的概念
二、递归算法用于解决的问题
可用递归解决的具体问题：
数据的定义形式是按递归定义的。如阶乘。
问题的解法按递归算法实现。如回溯算法。
数据结构的形式是按递归定义的。如树的遍历。
function jc(n: integer): longint;
begin
if (n = 0) then
jc := 1
else
jc := n * jc(n-1);
end;
procedure m-search(t: node)begin
if (t <> nil) then
begin
m-search();
visit(t);
m-search();
end;
end;
递归Pascal-递归递归的概念
三、递归算法的执行过程
Fac(5)
5*Fac(4)
4*Fac(3)
3*Fac(2)
2*Fac(1)
1*Fac(0)
1
=1
=1
=2
=6
=24
主程序
=120
递归Pascal-递归递归的概念
三、递归算法的执行过程
在递归调用之前，系统需完成三件事：
为被调用过程的局部变量分配存储区；
将所有的实在参数、返回地址等信息传递给被调用过程保存；
将控制转移到被调过程的入口。
从被调用过程返回调用过程之前，系统也应完成三件工作：
保存被调过程的计算结果；
释放被调过程的数据区；
依照被调过程保存的返回地址将控制转移到调用过程。
递归Pascal-递归递归的概念