程序設計中遞歸調用算法探究

曹耀輝

(陜西財經職業技術學院信息工程系,陜西咸陽 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-),男,陜西武功人,陜西財經職業技術學院信息工程系副教授,碩士,從事軟件工程研究。