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

曹耀輝

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

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

曹耀輝

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[3]程時(shí)興.IBM-PC匯編語(yǔ)言實(shí)用教程[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-),男,陜西武功人,陜西財(cái)經(jīng)職業(yè)技術(shù)學(xué)院信息工程系副教授,碩士,從事軟件工程研究。