基于C語言的遞歸與循環關系的研究

摘要本文闡述了作者對于算法設計中遞歸問題和循環問題的理解，同時討論了兩者間的轉換關系，并使用C語言對其中一種轉換方式進行了實驗，以求在相關算法的優化設計方面能夠有所提高。

關鍵詞遞歸 循環 C語言

中圖分類號:TP31文獻標識碼:A

遞歸作為一種正對實際問題的程序設計解決方案，在整個編程語言學習及程序設計方面有著極其重要的地位。而在實際的教學環節中對于這樣一種具有很高使用價值的編程技術，在講解上和學生理解上還存在著一定困難。

循環結構是結構化程序設計的三種結構之一，主要應用在處理某些需要重復執行特定語句的情況下，通常在使用循環時我們需要明確三個重要條件:

1> 循環的初始條件;

2> 循環的中止條件(或在什么情況下循環運行);

3> 程序有趨于結束的趨勢。

而遞歸作為一種算法，在數學上我們時這樣定義它的，以n的階乘為例:

0!=1(*)

n!=n*(n-1) 當n>0時 (**)

其中(*)稱為基本實例(基本實例的值必須是直接獲得的);(**)稱為遞歸歸約。遞歸被定義為:自身定義為一種含有自身簡化的形式。那么從形式上我們可以清楚的看到:

1> 每個遞歸定義必須有一個(或者多個)基本實例;

2> 遞歸歸約最終歸結到基本實例;

3> 在基本實例處停止遞歸。

從中我們不難發現遞歸的算法形式條件和循環的條件是非常類似的。

那么在運行遞歸函數時，邏輯上我們可以認為遞歸函數有無限的自身拷貝(當然這是受限的)，完成某個遞歸調用后，控制返回到先前的調用環境。這同循環算法在思想上也是異曲同工的。所以我們也完全可以編寫一個循環結構來替代遞歸。

造成這種可替代性的主要原因是因為目前為止的編譯系統處理遞歸函數時，在編譯之后都是自動將遞歸轉化為循環的。但是和循環不同的是，編譯后的遞歸需要創建一個內存棧來存儲遞歸過程中的臨時變量，對于遞歸函數的調用和返回操作，則分別對應棧的入棧和出棧。

因此任何一個遞歸程序都可以通過引入堆棧的形式來轉化為循環，這種轉化其實就是模擬計算機實現遞歸的過程。你可以考慮人腦來計算遞歸的過程:先倒過來向前遞歸，到達最初點以后再正過來向后遞推，堆棧的作用就是記住過程中的臨時變量。雖然這樣做只不過是模擬遞歸的執行過程，將原來由編譯器實現的事情在程序中用代碼實現了一遍，但是確實可以通過循環和堆棧的數據結構特性來實現遞歸的算法和遞歸函數的功能。

那么基于遞歸和循環的這種可以相互替代性，我們應當如何選用遞歸或循環呢?

在大多數編譯系統中遞歸會受棧(編譯系統自動分配)的大小限制，如果遞歸調用的次數很多，就不能使用遞歸了。一般情況下，遞歸效率不如循環高，主要是保存棧需要時間，調用函數也需要時間，再加上開辟棧的額外內存開銷，從而導致程序性能的降低。遞歸一般在算法或者數學模型是遞歸定義的情況下，為了方便編碼(主要是理解)才使用。但是我們也應該注意到，依靠棧和循環來模擬遞歸，在技術上可行，但在提高程序性能上，意義并不明顯(兩者在編譯后，代碼幾乎完全一樣)。只有使用真正意義上的非遞歸算法才能夠在本質上與遞歸區別開。

這里所謂的非遞歸算法就是指不引入堆棧等輔助空間進行計算的算法。更確切地說，非遞歸是指輔助的空間為0或1的算法(即輔助空間的規模和問題的輸入規模無關)。但是很遺憾，在目前可計算性理論發展的水平下事實上，一般只能對尾遞歸或單向遞歸的情形，都可利用循環的方法，將遞歸算法改為非遞歸算法。

當然，另外還有很多方法將遞歸轉化為遞推，例如利用Cooper變換和拓廣Cooper變換:

[Cooper變換]

輸入模式:

f(x) ≡ if b(x) then h(x)

else F(f(k(x))， g(x))

輸出模式:

f(x) ≡ G(x， e)

G(x， y) ≡ if b(x) then F(h(x)， y)

else G( k(x)， F(g(x)，y) )

其中:

x， k: TYPE1， k(x) -< x( 符號 -< 表示偏序)

y， G， h， g， f， F: TYPE2

b: boolean

e: F的右單位元，即F(x， e) = x

可用性條件:

(1)F滿足結合律，即F(F(x，y)，z) = F(x， F(y， z))

(2)F有右單位元e;

(3)b， h， g， k中都不含f

[拓廣的Cooper變換]

輸入模式:

f(x) ≡ if b(x) then h(x)

else if b1(x) then F1( f( k1(x) )， g1(x) )

...

else if bn(x)then Fn( f( kn(x) )， gn(x) )

else F0( f( k0(x) )，g0(x) )

輸出模式:

f(x) ≡ if b(x) then h(x)

else if b1(x) then G1( k1(x)， g1(x) )

...

else if bn(x) then Gn( kn(x)， gn(x) )

else G0( k0(x)， g0(x) )

對于所有的 0≤i≤n，

Gi( x， y) = if b(x) then Fi( h(x)， y )

else if b1(x) then Gi( k1(x)， F1( g1(x)， y ) )

...

else if bn(x) then Gi( kn(x)， Fn( gn(x)， y ) )

else Gi( k0(x)， F0( g0(x)， y ) )

其中:

對于所有的 0≤i≤n

x， ki: TYPE1， ki(x) -< x ( 符號-< 表示偏序)

gi， h， Fi， Gi， y: TYPE2

b， bj: boolean， 1≤j≤n

b(x)∧b1(x)∧……∧bn(x) = (空集)

b(x)∨b1(x)∨……∨bn(x) = (全集)

可用性條件:

(1)Fi滿足結合律，即Fi( Fj(x， y)， z ) = Fj( x， Fi(y， z) )， 0≤i， j≤n

(2)b， bj， h， gi， ki中都不含f， 0≤i≤n， 1≤j≤n

以及T1，T2變換，C變換，RR變換等等，在組合數學理論中已經研究的比較多了。也不再是本文的重點。對此有興趣的讀者可以閱讀一下參考書目(2)的第三章和第五章。

綜上所述，遞歸和循環無論在算法上還是在實現上都有著巨大的聯系，如采用棧的方法則可以實現所有遞歸和循環的轉換，但是如果只采用非遞歸算法的循環，則只能夠處理原始遞歸和一些可計算性較大的遞歸函數。

參考文獻

[1][美] Robert Sedgewick.C算法(第一卷).人民郵電出版社，ISBN0-201-31452-5.

[2][美] Kennety H.Rosen.離散數學及其應用.機械工業出版社，ISBN7-111-07577-3.

[3][美] Richard A Brualdi.組合數學.機械工業出版社，ISBN7-111-07569-2.

[4][美] Alfred V.Aho.數據結構與算法.清華大學出版社，ISBN7-302-07564-6.