曹耀輝

(陜西財經(jīng)職業(yè)技術(shù)學(xué)院信息工程系,陜西咸陽 712000)

程序設(shè)計中遞歸調(diào)用算法探究

曹耀輝

(陜西財經(jīng)職業(yè)技術(shù)學(xué)院信息工程系,陜西咸陽 712000)

目前計算機程序設(shè)計教材中很少提到遞歸調(diào)用算法,原因多為程序設(shè)計中遞歸調(diào)用算法十分抽象,以致廣大學(xué)生及編程人員難以理解,而遞歸調(diào)用算法在程序設(shè)計中又顯得十分重要,本文應(yīng)用實例說明遞歸調(diào)用算法內(nèi)部執(zhí)行過程,以便廣大學(xué)生及編程人員真正理解并掌握遞歸調(diào)用思想,從而利用遞歸調(diào)用算法解決實際問題。

程序設(shè)計;遞歸調(diào)用;算法;探究

在程序設(shè)計中,如果主程序調(diào)用子程序,而子程序直接地或間接地調(diào)用它自身,我們稱這種情況為程序的遞歸調(diào)用。在編程時,有時采用遞歸的思路進行編程往往能夠起到事半功倍的作用。但是,遞歸調(diào)用思想確實很難理解,以致在絕大多數(shù)計算機程序設(shè)計教材中很少提到遞歸調(diào)用算法,即使提到也只是泛泛地舉一兩個例子,并沒有較好地分析過程,以致于多數(shù)學(xué)生還是很難理解。尤其在Visual FoxPro程序設(shè)計教材中連遞歸調(diào)用算法都沒有提及,更談不上讓學(xué)生理解并掌握遞歸調(diào)用算法了。鑒于此,筆者針對Visual FoxPro程序設(shè)計中的遞歸調(diào)用算法內(nèi)部具體執(zhí)行過程作一個分析與探究,以便廣大程序設(shè)計者真正理解并掌握遞歸調(diào)用算法。

這里,研究一下如何編程計算X的階乘X!,下面先給出程序,同時給出分析。

運行主程序時,先給X提供一個正整數(shù)值,然后再計算其階乘,程序中用變量F存放X的階乘值,給階乘F賦初值1,當(dāng)然在本程序中階乘F的初值如何并不重要,也可以是其他值,這并不影響程序的運行結(jié)果,但F的初值必須具有,因為主程序第4行DO SUB WITH X,F中要調(diào)用子程序SUB1PRG,其中用到了帶參數(shù)子程序的調(diào)用,而帶參數(shù)子程序調(diào)用中的參數(shù)必須具有初值,以便給子程序SUB.PRG的形式參數(shù)傳遞初值,子程序的第一條語句PARAMETERS X,Y就是用來接收主程序MAIN.PRG中的調(diào)用語句DO SUB WITH X,F中X和Y的初值的。

子程序第一條語句PARAMETERS X,Y從主程序中得到X,F的初值后,主程序暫時中斷,處理子程序SUB.PRG。子程序SUB.PRG從第2行至第7行實際上是一個分支語句,對于一個正整數(shù)X,如果X不等于1,則X的階乘等于X-1的階乘與X之積,至于X-1的階乘又通過調(diào)用自身來實現(xiàn),依次類推,形成遞歸,這樣就把復(fù)雜問題逐步簡單化,直到X為1時,其階乘規(guī)定為1作為歸結(jié)點。執(zhí)行子程序最后一條語句RETURN時,返回到調(diào)用其程序的斷點接著往后繼續(xù)執(zhí)行,當(dāng)返回到主程序MAIN.PRG后,F的值就是X的階乘,接著執(zhí)行主程序第5行,輸出X的階乘值,則問題解決完畢。

下面再進行詳細(xì)分析程序的具體執(zhí)行過程,比如要計算3的階乘,子程序被調(diào)用了3次,為了說明問題,以下再寫出主程序及3次調(diào)用子程序的情況,盡管是同一子程序,但是3次被調(diào)用的情況不一樣,體現(xiàn)了程序的動態(tài)性,因此筆者還是將它寫出3次,在以下簡稱子程序(1)、子程序(2)、子程序(3),這在理解遞歸調(diào)用算法上非常有用。

首先,運行主程序,執(zhí)行第2條語句INPUT″X=″TO X,要求用戶通過鍵盤給變量X賦一個初值,這里我們給出初值3,也就是要計算3的階乘,執(zhí)行第3條語句F=1后,給變量 F賦初值1,執(zhí)行第4條語句DO SUB WITH X,F時調(diào)用子程序(1),將實在參數(shù)X和F的初值3和1分別傳遞給子程序(1)中的兩個形式參數(shù)X和Y,同時主程序暫時中斷,轉(zhuǎn)入子程序(1)執(zhí)行。

相應(yīng)地,子程序(1)的第1條語句PARAMETERS X,Y就是接收主程序第4條語句DO SUB WITH X,F中實在參數(shù)初值的語句,執(zhí)行后使兩個形式參數(shù)X和Y分別取得3和1,接著執(zhí)行下面的分支語句,這里因X的值為3(不等于1),故執(zhí)行IF…ELSE…ENDIF語句的第1支,也即IF和ELSE之間的兩條語句DO SUB WITH X-1,Y和 Y=Y3X,語句DO SUB WITH X-1,Y又調(diào)用它自身,從而形成遞歸調(diào)用,把計算X!的問題歸結(jié)為計算(X-1)!的問題,如果計算出(X-1)!值之后再乘以X即為X!的值。值得注意的是,語句DO SUB WITH X-1,Y在執(zhí)行時又調(diào)用它自身,為了便于分析,這里我們稱為調(diào)用子程序(2),當(dāng)然語句DO SUB WITH X-1,Y調(diào)用子程序(2)時,首先將實在參數(shù)X-1,Y的初值2和1傳遞給子程序(2)的第1條語句PARAMETERS X,Y中的形式參數(shù)X和Y,然后子程序(1)暫時中斷,轉(zhuǎn)入子程序(2)執(zhí)行。

子程序(2)的第1條語句PARAMETERS X,Y相應(yīng)的執(zhí)行后,使兩個形式參數(shù)X和 Y分別取得2和1,接著執(zhí)行下面的分支語句,這里因X的值為2(不等于1),故執(zhí)行IF…ELSE…ENDIF語句的第1支,也即 IF和 ELSE之間的兩條語句DO SUB WITH X-1,Y和Y=Y3X,語句DO SUB WITH X-1,Y又調(diào)用它自身,為了便于分析這里我們稱為調(diào)用子程序(3),當(dāng)然語句DO SUB WITH X-1,Y調(diào)用子程序(3)時,首先將實在參數(shù)X-1,Y的初值1和1傳遞給子程序(3)的第1條語句PARAMETERS X,Y中的形式參數(shù)X和Y,然后子程序(2)暫時中斷,轉(zhuǎn)入子程序(3)執(zhí)行。

子程序(3)的第1條語句PARAMETERS X,Y相應(yīng)的執(zhí)行后,使兩個形式參數(shù)X和 Y分別取得1和1,接著執(zhí)行下面的分支語句,這里因X的值為1(等于1),故執(zhí)行 IF…ELSE…ENDIF語句的第2支,也即 ELSE和 EN2 DIF之間的那條語句 Y=1,這樣就把問題歸結(jié)為計算1!的問題,而1!為1作為已知條件,也就是問題的歸結(jié)點,到此遞歸調(diào)用結(jié)束,然后逐級向上級程序返回。子程序(3)的最后一條語句RETURN執(zhí)行時即返回子程序(2)的斷點DO SUB WITH X-1,Y,主要作用是將變量Y的新值1帶回子程序(2),接著執(zhí)行子程序(2)中的語句Y=Y3X,子程序(3)執(zhí)行結(jié)束。

剛返回子程序(2)時,Y的值為1,接著執(zhí)行子程序(2)的語句 Y=Y3X,因為這時 Y的值為1,X的值為2,因此這條語句執(zhí)行完后,變量 Y的值就為2,即就是2!=2,然后執(zhí)行子程序(2)的最后一條語句RETURN,即返回子程序(1)的斷點DO SUB WITH X-1,Y,主要作用是將變量Y的新值2帶回子程序(1),接著執(zhí)行子程序(1)中的語句Y=Y3X,子程序(2)執(zhí)行結(jié)束。

剛返回子程序(1)時,Y的值為2,接著執(zhí)行子程序(1)的語句 Y=Y3X,因為這時 Y的值為2,X的值為3,因此這條語句執(zhí)行完后,變量 Y的值就為6,即就是3!=6,然后執(zhí)行子程序(1)的最后一條語句RETURN,即返回主程序MAIN.PRG的斷點DO SUB WITH X,F,主要作用是將變量Y的新值6帶回主程序,傳遞給主程序的變量F,同時子程序(1)執(zhí)行結(jié)束,接著執(zhí)行主程序中的語句?″該階乘是:″,F。

返回主程序時變量F得到返回值6,接著執(zhí)行主程序中的語句?″該階乘是:″,F時就會輸出結(jié)果″該階乘是:6″,到此3的階乘計算完畢,遞歸調(diào)用及返回過程結(jié)束。

以上通過計算3!的具體實例的詳細(xì)分析,使廣大程序愛好者清晰地理解了遞歸調(diào)用的思想,同理我們也就理解了用遞歸算法計算4!,5!,…,X!的內(nèi)部執(zhí)行過程。

遞歸調(diào)用算法的作用非同小可,在數(shù)學(xué)定理的證明、數(shù)學(xué)問題的求解上經(jīng)常會遇到遞歸調(diào)用算法,遞歸調(diào)用算法確實是解決許多數(shù)學(xué)問題的有力工具,其重要性不言而喻。通過上面算法實例的具體分析,使廣大編程愛好者從本質(zhì)上理解了遞歸調(diào)用算法,從而使他們能夠靈活利用遞歸調(diào)用算法解決實際問題,在編程中往往起到事半功倍的作用。

[1]田淑清.全國計算機等級考試二級教程-C語言程序設(shè)計[M].北京:高等教育出版社,1998.

[2]馬秋菊.C語言程序設(shè)計[M].北京:中國宇航出版社,2004.

[3]程時興.IBM-PC匯編語言實用教程[M].重慶:重慶大學(xué)出版社,2002.

[3]遞歸與斐波那契[EB/OL].http://ascii.javaeye.com/blog/627907,2010-3.

[4]循環(huán)(迭代)與遞歸的區(qū)別[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-),男,陜西武功人,陜西財經(jīng)職業(yè)技術(shù)學(xué)院信息工程系副教授,碩士,從事軟件工程研究。