遞歸和迭代對(duì)程序的影響

田　俊

摘要:在算法的分析與設(shè)計(jì)中,遞歸和迭代都是特別有力的工具,很多難解的問(wèn)題都是通過(guò)遞歸或迭代算法解出來(lái)的。本文在比較這兩種算法在不同情況下的可行性的基礎(chǔ)上,闡述了怎樣對(duì)這兩種算法進(jìn)行有效的選擇。

關(guān)鍵詞:遞歸算法 迭代算法 程序

0 引言

在算法分析與設(shè)計(jì)中,遞歸與迭代是我們解決循環(huán)問(wèn)題常用的兩種方法。那么,在既可以用遞歸算法又可以用迭代算法解決的問(wèn)題中,我們究竟該選用哪種算法呢?在程序設(shè)計(jì)中,我們不但講求代碼所能實(shí)現(xiàn)的功能,而且在實(shí)現(xiàn)相同功能的同時(shí),更注重優(yōu)化代碼、提高代碼的執(zhí)行效率。這也是我們?cè)谶x擇遞歸還是迭代思想時(shí)考慮的主要因素。

1 遞歸和迭代概述

如果一個(gè)問(wèn)題剛開(kāi)始難以解決,可以將其簡(jiǎn)化后再?lài)L試解決。如果這個(gè)過(guò)程可以重復(fù)進(jìn)行,問(wèn)題最終會(huì)變得容易處理。由此引出兩種不同的方法:遞歸和迭代。循環(huán)或迭代,是一種重復(fù)執(zhí)行一個(gè)過(guò)程的方法;遞歸是另一種方法。遞歸函數(shù)是通過(guò)調(diào)用函數(shù)自身來(lái)完成任務(wù),而且在每次調(diào)用自身時(shí)減少任務(wù)量。而迭代是循環(huán)的一種形式,這種循環(huán)不是由用戶輸入而控制,每次迭代步驟都必須將剩余的任務(wù)減少;也就是說(shuō),循環(huán)的每一步都必須執(zhí)行一個(gè)有限的過(guò)程,并留下較少的步驟。循環(huán)的進(jìn)度通常用一個(gè)在每次迭代時(shí)都進(jìn)行自增或自減的變量的值來(lái)衡量,直到到達(dá)預(yù)定的目標(biāo)為止。用遞歸算法表示許多問(wèn)題的求解方法時(shí)算法思想非常簡(jiǎn)潔。但是遞歸算法不僅時(shí)間效率非常差,而且由于遞歸算法是不斷的函數(shù)調(diào)用和函數(shù)返回過(guò)程,因此其實(shí)際的計(jì)算機(jī)運(yùn)行時(shí)間通常遠(yuǎn)大于循環(huán)方式算法的計(jì)算機(jī)運(yùn)行時(shí)間,甚至在有限的時(shí)間內(nèi)無(wú)法求解。這就存在一個(gè)把遞歸算法化為非遞歸算法的問(wèn)題。

2 需要用迭代消解遞歸的情況

遞歸算法特別適合于所研究的問(wèn)題或所處理的數(shù)據(jù)本身是遞歸定義的情況。然而,并不意味著這種遞歸定義保證遞歸算法是解決該問(wèn)題的最好方法。事實(shí)上,主要是因?yàn)槟媚欠N不合適的例子來(lái)解釋遞歸算法概念,從而造成了對(duì)程序設(shè)計(jì)中使用遞歸的普遍懷疑和否定態(tài)度,并把遞歸同低效等同起來(lái)。而且在遞歸算法中,往往會(huì)因?yàn)樽非蟠a短或者在求解問(wèn)題時(shí)一味追求規(guī)律性,多用了無(wú)用的壓棧和出棧的操作。比如用循環(huán)消解的尾遞歸,是多了無(wú)用的壓棧和出棧才使速度受損的;斐波那契數(shù)列計(jì)算的遞歸改循環(huán)迭代所帶來(lái)的速度大幅提升,是因?yàn)楦牡袅酥貜?fù)計(jì)算的毛病。假使一個(gè)遞歸過(guò)程中本身包含了大量冗余的操作,并且這個(gè)過(guò)程又可以用迭代來(lái)達(dá)到相同的效果。這時(shí),我們就一般用迭代來(lái)消解遞歸。也就是說(shuō)尾遞歸算法和單向遞歸算法可用迭代算法來(lái)代替?？梢杂靡粋€(gè)方案來(lái)描述人們力圖在其中避免使用算法遞歸的程序,這個(gè)方案展示了其構(gòu)成的模型。(1)式或等價(jià)的(2)式就是這個(gè)方案:

P≡ if B then (S;P)(1)

P≡(S; if B then P)(2)

要計(jì)算用簡(jiǎn)單遞歸關(guān)系定義的值時(shí),這種方案是很自然的。如下例:

Function F (I: integer ):integer;

Begin if I>0 then F:=I*F(I-1)

Else F:=1;

End(3)

很明顯,在這種情況下,遞歸可由簡(jiǎn)單迭代代替,即由下面的程序代替。

I:=0;F:=1;

While I

Begin I:=I+1;F:=I*F

End (4)

一般地,對(duì)應(yīng)于方案(1)或(2)的程序應(yīng)按照下列方案改寫(xiě):

P ≡(x:=x0;while B do S)

還有更復(fù)雜的遞歸構(gòu)造方案,這些方案可以并且應(yīng)該改寫(xiě)成迭代計(jì)算的形式。一個(gè)例子就是Fibonacci 數(shù)的計(jì)算,這些數(shù)是按遞歸關(guān)系定義的:

FIBn+1=FIBn+FIBn-1對(duì)n>0

而FIB1=1,FIB0=0,一個(gè)直接的自然的解法導(dǎo)致程序

function fib (n: integer): integer;

begin if n=0 then fib :=0else

if n=1 then fib :=1 else

fib:=fib(n-1)+fib(n-2)

end

以調(diào)用fib(n)來(lái)計(jì)算FIBn ,就引起這個(gè)函數(shù)過(guò)程的遞歸活動(dòng)。頻繁程度如何呢?我們注意到,對(duì)于n>1,每調(diào)用一次引起兩個(gè)新的調(diào)。因此,調(diào)用的總次數(shù)按指數(shù)增長(zhǎng),如下圖所示fib(5)的遞歸樹(shù)。這樣一個(gè)程序顯然是不實(shí)用的。

但顯見(jiàn),利用輔助變量x=FIBi與y=FIBi-1,就可以用迭代方案來(lái)計(jì)算Fibonicca 數(shù),而避免同一值的重復(fù)計(jì)算。

{ 對(duì)n>0計(jì)算x=FIBn}

i:=1;x:=1;y:=0;

while i

begin z:=x; i:=i+1;

x:=x + y; y:=z

end

(注意,對(duì)x, y, z的三個(gè)賦值,可以只表示成兩個(gè)賦值,而不需要輔助變量z :x:=x +y ; y:=x-y).由上述例子可以看出,當(dāng)存在明顯的迭代解法時(shí)要避免使用遞歸。

3 不需要消解的遞歸

那種盲目的消解遞歸,不惜一切代價(jià)躲避遞歸,認(rèn)為“遞歸的速度慢,為了提高速度,必須用?；蛘咂渌姆椒▉?lái)消解”的說(shuō)法是很片面的。如果一個(gè)遞歸過(guò)程用非遞歸的方法實(shí)現(xiàn)后,速度提高了,那只是因?yàn)檫f歸做了一些無(wú)用功。假使一個(gè)遞歸過(guò)程必須要用棧才能消解,那么完全模擬后的結(jié)果根本就不會(huì)對(duì)速度有任何提升,只會(huì)減慢;如果你改完后速度提升了,那只證明你的遞歸函數(shù)寫(xiě)的有問(wèn)題,如多了許多重復(fù)操作——打開(kāi)關(guān)閉文件、連接斷開(kāi)數(shù)據(jù)庫(kù),而這些完全可以放到遞歸外面?？梢栽诒举|(zhì)上是非遞歸的機(jī)器上實(shí)現(xiàn)遞歸過(guò)程這一事實(shí)本身就證明:為著實(shí)際目的,每一個(gè)遞歸程序都可以翻譯成純粹迭代的形式,但這包含著對(duì)遞歸棧的顯式處理,而這些運(yùn)算常常模糊了程序的本質(zhì),以致使它非常難以理解。

因此,是遞歸的而不是迭代的算法應(yīng)當(dāng)表述成遞歸過(guò)程。如漢諾塔問(wèn)題等。漢諾塔問(wèn)題的遞歸算法中有兩處遞歸調(diào)用,并且其中一處遞歸調(diào)用語(yǔ)句后還有其他語(yǔ)句,因此該遞歸算法不是尾遞歸或單向遞歸。要把這樣的遞歸算法轉(zhuǎn)化為非遞歸算法,并沒(méi)有提高程序運(yùn)行的速度,反而會(huì)使程序變得復(fù)雜難懂,這是不可取的。也就是說(shuō),很多遞歸算法并不容易改寫(xiě)成迭代程序:它們本質(zhì)上是遞歸的,沒(méi)有簡(jiǎn)單的迭代形式。這樣的遞歸算法不宜轉(zhuǎn)化為非遞歸算法。

4 結(jié)束語(yǔ)

說(shuō)到底,在我們選擇算法時(shí)應(yīng)該全面分析算法的可行性、效率、代碼優(yōu)化。在綜合了算法的各個(gè)因素后,選擇合適的算法來(lái)編寫(xiě)程序,這樣的程序才會(huì)達(dá)到優(yōu)化的效果。

參考文獻(xiàn):

[1]王曉東.算法分析與設(shè)計(jì)清華大學(xué)出版社.

[2]Alice E. Fischer DavidW .Egger 等著Applied C: An Introduction and More電子工業(yè)出版社.