6.2.2
递归子程序
在子程序嵌套的情况下,如果一个子程序调用的子程序就是它自身,就称为递归调用,这样的子程序称为递归子程序。
递归子程序对应于数学上对函数的递归定义,往往能设计出效率较高的程序,可完成相当复杂的计算,所以是很有用的。这里以阶乘函数为例,说明递归子程序的设计方法。
例6.7 编制计算N! (N>=0)的程序。
N!= N* (N-1) * (N-2) * … * 1
其递归定义如下:
求N!本身是一个子程序,由于N!是N和(N-1)!的乘积,所以为求(N-1)!必须递归调用求N!的子程序,但每次调用所使用的参数都不相同。
递归子程序的设计必须保证每次调用都不破坏以前调用时所用的参数和中间结果,所以一般把每次调用的参数、寄存器内容及所有的中间结果都存放在堆栈中。
我们把一次调用所保存的信息称为帧(frame),一般一帧包括所保存的寄存器内容、参数或参数地址和中间结果等。每次调用把一帧信息存入堆栈。
递归子程序中还必须包括基数的设置,当调用参数达到基数时,还必须有一条条件转移指令实现嵌套退出,以保证能按反向次序退出并返回主程序。
例6.7的程序动画如左示。
|