算法设计与分析--递归.ppt

递归
第3章递归
递归调用的内部实现原理
递归程序的阅读
递归转非递归
递归算法的设计
解递归方程
递归的定义
在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。
递归调用的内部实现原理
子程序调用的几种形式
(1)两次值传送方式
按指定类型为变参设置相应的存储空间,在执行调用时,将实参值传送给变参,在返回时将变参的值回传实参。
(2)地址传送方式
在内部将变参设置成一个地址,调用时首先执行地址传送,将实参的地址传送给变参,在子程序执行过程中,对变参的操作实际上变成所对应的实参的操作。
值的回传
①在执行调用时,系统至少执行如下操作:
,同时在栈顶为被调子程序的局部变量开辟空间;
:计算实参值,并赋给对应的栈顶的形参;
;
②在执行返回操作时,系统至少执行如下操作:
,将其值保存到回传变量中;
;
;
,从回传变量中取出保存的值传送给相应的变量或位置上。
子程序调用的内部实现
模拟系统栈方式
求m,n(m>n)的最大公因子的递归过程。
procedure GCD(m,n∶int;var h∶int)
begin
1∶if n=0
2∶ then begin h←m; write(h); end
3∶else call GCD(n,m mod n,h);
4∶endp;
递归程序的阅读
call GCD(28,6,X)执行过程
指令流方式
GCD(100,18,x)执行write(x)的运行过程,
指令流方式
指令流方式
对下面的递归过程,
写出调用P(3)的运行结果。
procedure P(w∶int);
begin
if w>0 then
begin
call P(w-1);
write(w);
call P(w-1);
end;
endp;