程序设计中递归调用算法探究

曹耀辉

(陕西财经职业技术学院信息工程系,陕西咸阳 712000)

程序设计中递归调用算法探究

曹耀辉

(陕西财经职业技术学院信息工程系,陕西咸阳 712000)

目前计算机程序设计教材中很少提到递归调用算法,原因多为程序设计中递归调用算法十分抽象,以致广大学生及编程人员难以理解,而递归调用算法在程序设计中又显得十分重要,本文应用实例说明递归调用算法内部执行过程,以便广大学生及编程人员真正理解并掌握递归调用思想,从而利用递归调用算法解决实际问题。

程序设计;递归调用;算法;探究

在程序设计中,如果主程序调用子程序,而子程序直接地或间接地调用它自身,我们称这种情况为程序的递归调用。在编程时,有时采用递归的思路进行编程往往能够起到事半功倍的作用。但是,递归调用思想确实很难理解,以致在绝大多数计算机程序设计教材中很少提到递归调用算法,即使提到也只是泛泛地举一两个例子,并没有较好地分析过程,以致于多数学生还是很难理解。尤其在Visual FoxPro程序设计教材中连递归调用算法都没有提及,更谈不上让学生理解并掌握递归调用算法了。鉴于此,笔者针对Visual FoxPro程序设计中的递归调用算法内部具体执行过程作一个分析与探究,以便广大程序设计者真正理解并掌握递归调用算法。

这里,研究一下如何编程计算X的阶乘X!,下面先给出程序,同时给出分析。

运行主程序时,先给X提供一个正整数值,然后再计算其阶乘,程序中用变量F存放X的阶乘值,给阶乘F赋初值1,当然在本程序中阶乘F的初值如何并不重要,也可以是其他值,这并不影响程序的运行结果,但F的初值必须具有,因为主程序第4行DO SUB WITH X,F中要调用子程序SUB1PRG,其中用到了带参数子程序的调用,而带参数子程序调用中的参数必须具有初值,以便给子程序SUB.PRG的形式参数传递初值,子程序的第一条语句PARAMETERS X,Y就是用来接收主程序MAIN.PRG中的调用语句DO SUB WITH X,F中X和Y的初值的。

子程序第一条语句PARAMETERS X,Y从主程序中得到X,F的初值后,主程序暂时中断,处理子程序SUB.PRG。子程序SUB.PRG从第2行至第7行实际上是一个分支语句,对于一个正整数X,如果X不等于1,则X的阶乘等于X-1的阶乘与X之积,至于X-1的阶乘又通过调用自身来实现,依次类推,形成递归,这样就把复杂问题逐步简单化,直到X为1时,其阶乘规定为1作为归结点。执行子程序最后一条语句RETURN时,返回到调用其程序的断点接着往后继续执行,当返回到主程序MAIN.PRG后,F的值就是X的阶乘,接着执行主程序第5行,输出X的阶乘值,则问题解决完毕。

下面再进行详细分析程序的具体执行过程,比如要计算3的阶乘,子程序被调用了3次,为了说明问题,以下再写出主程序及3次调用子程序的情况,尽管是同一子程序,但是3次被调用的情况不一样,体现了程序的动态性,因此笔者还是将它写出3次,在以下简称子程序(1)、子程序(2)、子程序(3),这在理解递归调用算法上非常有用。

首先,运行主程序,执行第2条语句INPUT″X=″TO X,要求用户通过键盘给变量X赋一个初值,这里我们给出初值3,也就是要计算3的阶乘,执行第3条语句F=1后,给变量 F赋初值1,执行第4条语句DO SUB WITH X,F时调用子程序(1),将实在参数X和F的初值3和1分别传递给子程序(1)中的两个形式参数X和Y,同时主程序暂时中断,转入子程序(1)执行。

相应地,子程序(1)的第1条语句PARAMETERS X,Y就是接收主程序第4条语句DO SUB WITH X,F中实在参数初值的语句,执行后使两个形式参数X和Y分别取得3和1,接着执行下面的分支语句,这里因X的值为3(不等于1),故执行IF…ELSE…ENDIF语句的第1支,也即IF和ELSE之间的两条语句DO SUB WITH X-1,Y和 Y=Y3X,语句DO SUB WITH X-1,Y又调用它自身,从而形成递归调用,把计算X!的问题归结为计算(X-1)!的问题,如果计算出(X-1)!值之后再乘以X即为X!的值。值得注意的是,语句DO SUB WITH X-1,Y在执行时又调用它自身,为了便于分析,这里我们称为调用子程序(2),当然语句DO SUB WITH X-1,Y调用子程序(2)时,首先将实在参数X-1,Y的初值2和1传递给子程序(2)的第1条语句PARAMETERS X,Y中的形式参数X和Y,然后子程序(1)暂时中断,转入子程序(2)执行。

子程序(2)的第1条语句PARAMETERS X,Y相应的执行后,使两个形式参数X和 Y分别取得2和1,接着执行下面的分支语句,这里因X的值为2(不等于1),故执行IF…ELSE…ENDIF语句的第1支,也即 IF和 ELSE之间的两条语句DO SUB WITH X-1,Y和Y=Y3X,语句DO SUB WITH X-1,Y又调用它自身,为了便于分析这里我们称为调用子程序(3),当然语句DO SUB WITH X-1,Y调用子程序(3)时,首先将实在参数X-1,Y的初值1和1传递给子程序(3)的第1条语句PARAMETERS X,Y中的形式参数X和Y,然后子程序(2)暂时中断,转入子程序(3)执行。

子程序(3)的第1条语句PARAMETERS X,Y相应的执行后,使两个形式参数X和 Y分别取得1和1,接着执行下面的分支语句,这里因X的值为1(等于1),故执行 IF…ELSE…ENDIF语句的第2支,也即 ELSE和 EN2 DIF之间的那条语句 Y=1,这样就把问题归结为计算1!的问题,而1!为1作为已知条件,也就是问题的归结点,到此递归调用结束,然后逐级向上级程序返回。子程序(3)的最后一条语句RETURN执行时即返回子程序(2)的断点DO SUB WITH X-1,Y,主要作用是将变量Y的新值1带回子程序(2),接着执行子程序(2)中的语句Y=Y3X,子程序(3)执行结束。

刚返回子程序(2)时,Y的值为1,接着执行子程序(2)的语句 Y=Y3X,因为这时 Y的值为1,X的值为2,因此这条语句执行完后,变量 Y的值就为2,即就是2!=2,然后执行子程序(2)的最后一条语句RETURN,即返回子程序(1)的断点DO SUB WITH X-1,Y,主要作用是将变量Y的新值2带回子程序(1),接着执行子程序(1)中的语句Y=Y3X,子程序(2)执行结束。

刚返回子程序(1)时,Y的值为2,接着执行子程序(1)的语句 Y=Y3X,因为这时 Y的值为2,X的值为3,因此这条语句执行完后,变量 Y的值就为6,即就是3!=6,然后执行子程序(1)的最后一条语句RETURN,即返回主程序MAIN.PRG的断点DO SUB WITH X,F,主要作用是将变量Y的新值6带回主程序,传递给主程序的变量F,同时子程序(1)执行结束,接着执行主程序中的语句?″该阶乘是:″,F。

返回主程序时变量F得到返回值6,接着执行主程序中的语句?″该阶乘是:″,F时就会输出结果″该阶乘是:6″,到此3的阶乘计算完毕,递归调用及返回过程结束。

以上通过计算3!的具体实例的详细分析,使广大程序爱好者清晰地理解了递归调用的思想,同理我们也就理解了用递归算法计算4!,5!,…,X!的内部执行过程。

递归调用算法的作用非同小可,在数学定理的证明、数学问题的求解上经常会遇到递归调用算法,递归调用算法确实是解决许多数学问题的有力工具,其重要性不言而喻。通过上面算法实例的具体分析,使广大编程爱好者从本质上理解了递归调用算法,从而使他们能够灵活利用递归调用算法解决实际问题,在编程中往往起到事半功倍的作用。

[1]田淑清.全国计算机等级考试二级教程-C语言程序设计[M].北京:高等教育出版社,1998.

[2]马秋菊.C语言程序设计[M].北京:中国宇航出版社,2004.

[3]程时兴.IBM-PC汇编语言实用教程[M].重庆:重庆大学出版社,2002.

[3]递归与斐波那契[EB/OL].http://ascii.javaeye.com/blog/627907,2010-3.

[4]循环(迭代)与递归的区别[EB/OL].http://summerbell.javaeye.com/blog/492852,2009-10.

Exploration on the Recursive Transfer Algorithm in Program Design

CAO Yao-hui
(Department of Information Engineering,Shaanxi Vocational Technical College of Finance&Economics,Xianyang 712000,China)

Due to the characteristics of abstraction and abstruseness,the recursive transfer algorithm is seldom referred in the teaching material of computer programming.However,the recursive transfer algorithm is very important in program design.This paper explains the inner execution process of the algorithm with detailed examples,in order to make college students and programmers fully understand and master the conception of recursive transfer,thus solve practical problems with the re2 cursive transfer algorithm.

program design;recursive transfer;algorithm;exploration

TP311

A

1008-178X(2011)03-0046-03

2011-04-14

曹耀辉 (1969-),男,陕西武功人,陕西财经职业技术学院信息工程系副教授,硕士,从事软件工程研究。