陳韶鈺 孫娟

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

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

中圖分類號(hào)：TP3? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）13-0202-03

1 遞歸算法的概述

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

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

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

2 遞歸算法的特點(diǎn)

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

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

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

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

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

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

例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：使用非尾遞歸實(shí)現(xiàn)n！

int jiecheng3（int n）

{

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

return 1;

else

return n*jiecheng3（n-1）;

}

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

int jiecheng（int n，int a）

{

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

}

算法3：利用循環(huán)實(shí)現(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++;

}

}

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

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

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

例3：n階漢諾塔問(wèn)題

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

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

{

println（n+”號(hào)”+”from”+from+”to”+to）;

}

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

{

if（n==1）

move（A，1，C）;//將編號(hào)為1的圓盤從A移到C

else{

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

move（A，n，C）;//將編號(hào)n的圓盤從A移到C

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

}

}

算法2：利用非遞歸算法實(shí)現(xiàn)漢諾塔問(wè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）{//將編號(hào)為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）;//將編號(hào)n的圓盤從A移到C

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

a=s[top].y;

b=s[top].x;

c=s[top].z;

top--;

}

}

}

例4：中序遍歷二叉樹(shù)

算法1：使用遞歸算法中序遍歷二叉樹(shù)

void inordertraverse（BiTree t）

{

if（t）

{

inordertraverse（ t->leftchild）;//遍歷左子樹(shù)

visit（t->data）;

inordertraverse（ t->rightchild）;//遍歷右子樹(shù)

}

}

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

void inordertraverse（BiTree? t）

{

Initstack（s）;

BiTree p=t;

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

if（p）{//根指針進(jìn)棧，遍歷左子樹(shù)

Push（s，p）;

p=p->leftchild;

}

else//根指針退棧，遍歷右子樹(shù)

{

Pop（s，p）;

visit（p->data）;

p=p->rightchild;

}

}

return;

}

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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