遞歸算法的非遞歸化剖析

陳韶鈺 孫娟

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

關(guān)鍵詞：遞歸算法;非遞歸化;尾遞歸;迭代;非尾遞歸;棧

中圖分類號：TP3? ? ? ? 文獻標(biāo)識碼：A

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

1 遞歸算法的概述

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

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

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

2 遞歸算法的特點

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

3 遞歸算法轉(zhuǎn)換為非遞歸算法的典型案例

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

（1）尾遞歸轉(zhuǎn)換成非遞歸算法

尾遞歸就是當(dāng)遞歸調(diào)用時最后執(zhí)行的語句是遞歸語句并且函數(shù)體中包含遞歸體的返回值不是表達式的一部分。在回歸的過程中，尾遞歸函數(shù)不需要任何操作?，F(xiàn)在很多的編譯器利用這一特點，使得代碼得到優(yōu)化。

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

例1：求最大公約數(shù)

算法1：利用尾遞歸求最大公約數(shù)

int gcd1（int big，int small）

{

if（big%small==0）

return? small;

else

Return gcd（small，big%small）;

}

算法2：利用循環(huán)求最大公約數(shù)

int gcd2（int a，int b）

{

while（b）

{

int t=a%b;

a=b;

b=t;

}

return a;

}

例2：求解n！

算法1：使用非尾遞歸實現(xiàn)n！

int jiecheng3（int n）

{

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

return 1;

else

return n*jiecheng3（n-1）;

}

算法2：利用尾遞歸實現(xiàn)n！

int jiecheng（int n，int a）

{

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

}

算法3：利用循環(huán)實現(xiàn)非遞歸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++;

}

}

從上面兩個例子可以看出，實現(xiàn)尾遞歸往往需要改寫遞歸函數(shù)，確保最后一步調(diào)用自身。要把普通的遞歸函數(shù)轉(zhuǎn)換為尾遞歸函數(shù)就須把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)?？傊?，凡是能改寫成尾遞歸的函數(shù)在非遞歸化時，都能用循環(huán)實現(xiàn)。雖然有些函數(shù)可以改寫成尾遞歸，但是在一定程度上降低了程序的可讀性。

（2）非尾遞歸函數(shù)借助棧來實現(xiàn)非遞歸化

顧名思義，非尾遞歸是遞歸執(zhí)行不是最后一句或?qū)儆诒磉_式的一部分。對于非尾遞歸而言，遞歸的過程是編譯器處理了壓棧和出棧的操作，轉(zhuǎn)換為迭代函數(shù)就需要手動地處理壓棧和出棧。

例3：n階漢諾塔問題

算法1：利用遞歸算法實現(xiàn)漢諾塔問題

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：利用非遞歸算法實現(xiàn)漢諾塔問題

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 遞歸算法與非遞歸算法的比較

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

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

5 結(jié)束語

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

參考文獻：

[1] 李瑩，孫承福.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2013.

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

[3] 施伯樂，等.數(shù)據(jù)結(jié)構(gòu)[M].上海：復(fù)旦大學(xué)出版社，1988.

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

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

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

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

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

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

【通聯(lián)編輯：代影】