遞歸算法的非遞歸化剖析

陳韶鈺 孫娟

摘要：在數據結構的教學中，我們經常用到遞歸，例如廣義表，二叉樹等，但是在課本中講到遞歸算法的非遞歸化卻寥寥數語，并且很多學生也問到這個問題。該文針對這一情況研究遞歸函數的非遞歸化。該文根據是否是尾遞歸進行分類，重點講解兩種不同的非遞歸化方法，其中一種轉換成循環來實現非遞歸化，但是對于復雜的非尾遞歸則使用棧來模擬系統棧的工作方式來實現非遞歸化，最后給出遞歸和非遞歸化的比較，根據問題的實際情況選擇是否采用遞歸。

關鍵詞：遞歸算法;非遞歸化;尾遞歸;迭代;非尾遞歸;棧

中圖分類號：TP3? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）13-0202-03

1 遞歸算法的概述

什么是遞歸？有這樣一個非常典型的例子：從前有座山，山上有座廟，廟里有個老和尚，老和尚在給小和尚講故事，故事講的是從前有座山，山上有座廟，廟里有個老和尚，老和尚在給小和尚講故事，故事講的是......遞歸函數就是一個直接調用自己或通過一系列的調用語句間接調用自己的函數。遞歸函數包含三種：第一，有很多遞歸定義的數學函數，例如階乘，斐波那契數列;第二，有本身具有遞歸特性的數據結構，例如二叉樹，廣義表等;第三種有些問題遞歸求解比迭代求解更加簡單，例如Hanoi塔問題，八皇后問題等。

此外，遞歸有三個要素：第一，遞歸邊界條件：確定遞歸到何時終止，即遞歸出口;第二，遞歸模式：大問題如何分解為小問題的，即遞歸體;第三，遞歸的調用次數必須是有限的，每次遞歸調用后必須越來越接近某種限制條件。實際上，遞歸就是把不好解決的復雜問題分解為一個或多個小問題，再把這些小問題分解成更小的問題，直到每個小問題都可以直接解決。

在執行遞歸算法時，它包括遞推和回歸兩個過程。在進行遞推過程中，就是將大問題分解為若干小問題，再進行求解，且必須要有終止遞歸的條件;在進行回歸時，得到小問題的解，并且依次返回，求得較大問題的解，最后取得最大問題的解。

2 遞歸算法的特點

遞歸使得程序簡潔明了，理解起來比較輕松，但是遞歸算法中來回切換函數調用現場浪費時間，并且系統提供棧來保存執行現場需要大量的空間。首先，系統設立一個遞歸工作棧來保證遞歸函數的正確執行。該系統工作棧是遞歸函數運行期間使用的數據存儲區。當調用一個遞歸函數時，系統會自動構建一個工作記錄，稱為棧幀，棧幀放在棧的最上面。開始的時候，棧幀僅僅存放返回地址和指向上一個幀的指針。每進入一層遞歸，就把新的記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄（即把棧幀刪除），直到程序控制返回原調用函數。于是，遞歸實現的空間效率并不高，又因為頻繁的壓棧和出棧時間開銷也非常大。總之，遞歸存在一個致命的缺點就是，遞歸的深度太深會導致堆棧溢出。

3 遞歸算法轉換為非遞歸算法的典型案例

在教學過程中，很多同學都以為使用棧將遞歸算法轉換為非遞歸算法，其實這種想法是錯誤的。遞歸算法分為尾遞歸和非尾遞歸。尾遞歸直接用循環來實現遞歸不需要棧來輔助，非尾遞歸則要使用棧來實現非遞歸算法。

（1）尾遞歸轉換成非遞歸算法

尾遞歸就是當遞歸調用時最后執行的語句是遞歸語句并且函數體中包含遞歸體的返回值不是表達式的一部分。在回歸的過程中，尾遞歸函數不需要任何操作。現在很多的編譯器利用這一特點，使得代碼得到優化。

尾遞歸的工作原理：當編譯器檢測到是尾遞歸函數調用時，每一層遞歸信息構成的工作記錄就覆蓋棧頂記錄，不會增加遞歸的深度。于是，每進入一層遞歸，棧頂存放的就是最后一條準備執行的記錄，這也就是說尾遞歸的棧的深度為1.但是這些并不是說明尾遞歸不需要棧，只是棧幀沒有其他的事情可以做，所以可以用循環來實現非遞歸化。也就是說，每一次遞歸調用只需要覆蓋棧幀，大大縮減了棧空間，所以非遞歸化時不需要手動的壓棧和出棧，大大提高了運行的效率。

例1：求最大公約數

算法1：利用尾遞歸求最大公約數

int gcd1（int big，int small）

{

if（big%small==0）

return? small;

else

Return gcd（small，big%small）;

}

算法2：利用循環求最大公約數

int gcd2（int a，int b）

{

while（b）

{

int t=a%b;

a=b;

b=t;

}

return a;

}

例2：求解n！

算法1：使用非尾遞歸實現n！

int jiecheng3（int n）

{

if（n==0||n==1）

return 1;

else

return n*jiecheng3（n-1）;

}

算法2：利用尾遞歸實現n！

int jiecheng（int n，int a）

{

return （n==1）？a：jiecheng（n-1，n*a）;

}

算法3：利用循環實現非遞歸n！

int jiecheng2（int n）

{

int result=1;

if（n<0）

return 0;

else if（n==0||n==1）

return 1;

int i=1;

While（n>=i）

{

result=result*i;

i++;

}

}

從上面兩個例子可以看出，實現尾遞歸往往需要改寫遞歸函數，確保最后一步調用自身。要把普通的遞歸函數轉換為尾遞歸函數就須把所有用到的內部變量改寫成函數的參數。總之，凡是能改寫成尾遞歸的函數在非遞歸化時，都能用循環實現。雖然有些函數可以改寫成尾遞歸，但是在一定程度上降低了程序的可讀性。

（2）非尾遞歸函數借助棧來實現非遞歸化

顧名思義，非尾遞歸是遞歸執行不是最后一句或屬于表達式的一部分。對于非尾遞歸而言，遞歸的過程是編譯器處理了壓棧和出棧的操作，轉換為迭代函數就需要手動地處理壓棧和出棧。

例3：n階漢諾塔問題

算法1：利用遞歸算法實現漢諾塔問題

Void move（char from，int n，char to）

{

println（n+”號”+”from”+from+”to”+to）;

}

void hanoi（int n，char A，char B，char C）

{

if（n==1）

move（A，1，C）;//將編號為1的圓盤從A移到C

else{

hanoi（n-1，A，C，B）;//將編號為n-1的圓盤，借助C盤從A移到B

move（A，n，C）;//將編號n的圓盤從A移到C

hanoi（n-1，B，A，C）;//將編號為n-1的圓盤，借助A盤從B移到A

}

}

算法2：利用非遞歸算法實現漢諾塔問題

struct act{

int num;

char x，y，z;

}s[max];

void hanoi（int n，char a，char b，char c）

{

int top=-1，count=0;

While（）

{

if（n>0）{//將編號為n-1的圓盤，借助C盤從A移到B

s[++top].num=n--;

s[top].x=a;

s[top].y=b;

s[top].z=c;

a=s[top].x;

b=s[top].y;

c=s[top].z;

}

else{

println（“%d：%d%c->%c”，++count，s[top].num，s[top].x，s[top].z）;//將編號n的圓盤從A移到C

n=s[top].num-1;//將編號為n-1的圓盤，借助A盤從B移到A

a=s[top].y;

b=s[top].x;

c=s[top].z;

top--;

}

}

}

例4：中序遍歷二叉樹

算法1：使用遞歸算法中序遍歷二叉樹

void inordertraverse（BiTree t）

{

if（t）

{

inordertraverse（ t->leftchild）;//遍歷左子樹

visit（t->data）;

inordertraverse（ t->rightchild）;//遍歷右子樹

}

}

算法2：使用非遞歸算法中序遍歷二叉樹

void inordertraverse（BiTree? t）

{

Initstack（s）;

BiTree p=t;

while（p||！StackEmpty（s））{

if（p）{//根指針進棧，遍歷左子樹

Push（s，p）;

p=p->leftchild;

}

else//根指針退棧，遍歷右子樹

{

Pop（s，p）;

visit（p->data）;

p=p->rightchild;

}

}

return;

}

4 遞歸算法與非遞歸算法的比較

由上述例子可以發現，遞歸方式設計的算法實現簡潔，思路清晰，具有良好的可讀性和可維護性，很容易證明該算法的正確性。但是，遞歸程序的執行效率一般低于非遞歸程序。尤其是遞歸深度較深時，就造成空間耗費大，這是遞歸算法最致命的弱點。

在要求執行效率比較高的情況下，我們一般選用非遞歸算法。根據尾遞歸的工作原理，遞歸所使用的棧空間就很大程度的縮減了，運行當中雖然利用到了堆棧，但是棧的深度為1。這樣在轉化為非遞歸化函數時，利用迭代就可以實現非遞歸化，這樣運行效率會變得很高。非尾遞歸利用棧來實現遞歸的非遞歸化，手動的壓棧和出棧，難于編寫，出錯率高。理論上，遞歸算法一般可轉化為非遞歸算法，但是有一些算法很難實現非遞歸化，所以要根據實際情況選擇是遞歸還是非遞歸。

5 結束語

在數據結構的教學中，遞歸算法的非遞歸化一直是教學中的重點和難點。在遇到一個問題時，要根據具體情況具體分析看是否使用遞歸算法。本文首先分析遞歸的特點，然后分析遞歸轉化為非遞歸的兩種方式，使學生很容易掌握遞歸函數的非遞歸化。

參考文獻：

[1] 李瑩，孫承福.數據結構[M].北京：清華大學出版社，2013.

[2] 高漢平，方志雄.從遞歸算法到非遞歸的變換[J].黃岡師范學院學報，2002，22（3）：47-50.

[3] 施伯樂，等.數據結構[M].上海：復旦大學出版社，1988.

[4] 孟林，尹德輝.遞歸算法本質及非遞化的一般規律[J].福建電腦，2004，20（1）：12-46.

[5] 高大鵬.C語言教學中的語言技巧[J].科技信息，2012（27）：217，525.

[6] 周法國，韓智，高天.遞歸算法設計思想與策略分析[J].軟件導刊，2017，16（10）：35-38.

[7] 李云鶴，武善玉，鐘鳴.最優二叉樹編譯碼確定的一種新方法[J].茂名學院學報，2003，13（4）：42-44，64.

[8] 高鷺，周李涌.遞歸算法及其轉化為非遞歸算法的分析[J].科技資訊，2008，6（30）：210.

[9] 姚俊明，邢丹，厲群，等.數據結構課程中遞歸教學的深入探討[J].電腦知識與技術，2011，7（14）：3382-3383，3385.

【通聯編輯：代影】