張建波

摘 要：提出一種把遞歸過(guò)程轉(zhuǎn)換為非遞歸過(guò)程的方法——遞歸樹法，畫出遞歸過(guò)程的遞歸樹，然后通過(guò)對(duì)遞歸樹的后根序遍歷實(shí)現(xiàn)遞歸過(guò)程的非遞歸化，最后通過(guò)案例說(shuō)明該方法的可行性和有效性。

關(guān)鍵詞：遞歸；遞歸過(guò)程；非遞歸化；遞歸樹

0 引 言

遞歸有思路清晰、代碼簡(jiǎn)潔、易于理解等特點(diǎn)，是很多算法設(shè)計(jì)策略（如分治、回溯等）的核心內(nèi)容，但是遞歸過(guò)程在計(jì)算機(jī)中實(shí)現(xiàn)時(shí)需要多次調(diào)用自身，增加了時(shí)空開銷。很多學(xué)者對(duì)遞歸過(guò)程進(jìn)行了深入研究[1-4]，部分學(xué)者提出了一些遞歸過(guò)程的非遞歸化方法[4]。文獻(xiàn)[3]和[5]雖然能很好地描述遞歸過(guò)程，但沒(méi)有給出如何轉(zhuǎn)換為非遞歸過(guò)程的一般方法；文獻(xiàn)[4]提出了模仿法，該方法從簡(jiǎn)單實(shí)例入手，逐步過(guò)渡到較復(fù)雜的遞歸算法，初學(xué)者容易理解，但不能對(duì)復(fù)雜的遞歸過(guò)程進(jìn)行直觀分析。

由于遞歸樹[2-3]作為研究遞歸過(guò)程的一種圖形化方法，具有直觀、簡(jiǎn)單等特點(diǎn)。筆者在此基礎(chǔ)上提出一種基于遞歸樹的遞歸過(guò)程的非遞歸化方法，該方法通過(guò)對(duì)遞歸樹后根序遍歷的思想實(shí)現(xiàn)遞歸過(guò)程的非遞歸化，具有直觀、易于理解的特點(diǎn)。

1 遞歸與遞歸樹

1.1 遞歸及遞歸過(guò)程的設(shè)計(jì)

一個(gè)問(wèn)題的解法可以通過(guò)把該問(wèn)題劃分成若干子問(wèn)題，若子問(wèn)題比較簡(jiǎn)單，則直接求解；否則，采用與原問(wèn)題相同的方法對(duì)這些子問(wèn)題進(jìn)行再劃分、求解，依次類推，直到子問(wèn)題變得較為簡(jiǎn)單，可以直接求解，當(dāng)求出所有子問(wèn)題的解后再對(duì)其進(jìn)行匯總即可得到原問(wèn)題的解，則稱該問(wèn)題為遞歸問(wèn)題[5]。在計(jì)算機(jī)上，人們通常采用遞歸方法來(lái)求解遞歸問(wèn)題，設(shè)計(jì)出的算法稱為遞歸算法。

在遞歸方法中，遞推動(dòng)作和結(jié)束條件是兩個(gè)重要組成部分。結(jié)束條件是指子問(wèn)題比較簡(jiǎn)單、不必再劃分成若干更小的子問(wèn)題時(shí)應(yīng)滿足的條件，也就是說(shuō)，當(dāng)子問(wèn)題滿足結(jié)束條件時(shí)可以直接求解。當(dāng)子問(wèn)題不滿足結(jié)束條件，還需要?jiǎng)澐殖筛?jiǎn)單的子問(wèn)題時(shí)需要執(zhí)行的操作步驟稱為遞推動(dòng)作。遞推動(dòng)作必須使遞歸算法能夠逐步到達(dá)結(jié)束條件。遞歸算法的一般模型為：

algorithm （） {

if （） /* 遞歸的結(jié)束條件 */

return （direct value）； /* 直接求解，并返回結(jié)果 */

else /* 遞歸 */

return （（parameter exchange））； /* 遞推動(dòng)作 */

}

遞歸的整個(gè)過(guò)程可分為兩個(gè)子過(guò)程：遞推過(guò)程和回歸過(guò)程。當(dāng)不滿足結(jié)束條件時(shí)，遞歸過(guò)程需要不斷執(zhí)行遞推動(dòng)作的過(guò)程為遞推過(guò)程；當(dāng)滿足結(jié)束條件時(shí)停止遞推動(dòng)作并沿遞推過(guò)程的逆過(guò)程進(jìn)行回溯的過(guò)程為回歸過(guò)程。遞推過(guò)程是對(duì)子問(wèn)題不斷細(xì)化使其逐步向結(jié)束條件靠近的過(guò)程；回歸過(guò)程是返回各子問(wèn)題的結(jié)果并匯總直到得出問(wèn)題最終解的過(guò)程。在一些復(fù)雜的遞歸算法中，遞推過(guò)程和回歸過(guò)程是交替出現(xiàn)的。

1.2 遞歸樹及其構(gòu)建

在計(jì)算機(jī)中，遞歸調(diào)用由若干個(gè)子遞歸調(diào)用組成，而子遞歸又有更下一層的子遞歸調(diào)用，這種逐層調(diào)用的軌跡可以用遞歸樹來(lái)刻畫。

遞歸樹是一種有序樹，樹根為遞歸算法的入口，根的值為遞歸參數(shù)值，如果遞歸參數(shù)值滿足結(jié)束條件，則開始回歸過(guò)程，此時(shí)根結(jié)點(diǎn)也是葉子結(jié)點(diǎn)；否則，遞歸算法需要調(diào)用自身若干次，每調(diào)用一次就相當(dāng)于樹根多了一個(gè)分支，即產(chǎn)成一棵子樹；每棵子樹也是遞歸樹。

遞歸樹是研究遞歸問(wèn)題與遞歸算法之間的一座橋梁。在分析具體問(wèn)題時(shí)，我們首先從根結(jié)點(diǎn)出發(fā)，按照遞歸的遞推過(guò)程不斷建立并擴(kuò)展遞歸樹，當(dāng)滿足結(jié)束條件時(shí)，該遞歸樹的根結(jié)點(diǎn)就成了葉子結(jié)點(diǎn)，然后根據(jù)建樹的逆序過(guò)程，不斷向根部返回并得到最終解。

與一般的非遞歸算法的分析方法——“單步跟蹤法”不同，遞歸樹可以直觀、清晰地描述遞歸算法的整個(gè)過(guò)程。對(duì)于一般的非遞歸算法，設(shè)計(jì)者常用單步跟蹤法動(dòng)態(tài)演示算法的執(zhí)行過(guò)程；但在遞歸算法中，由于不同層次遞歸時(shí)的參數(shù)是不一樣的，對(duì)于層數(shù)較多、遞推過(guò)程和回歸過(guò)程交替出現(xiàn)的遞歸算法，“單步跟蹤”法容易導(dǎo)致設(shè)計(jì)者對(duì)當(dāng)前調(diào)用環(huán)境中的參數(shù)產(chǎn)生混亂，因此，遞歸樹法可以有效避免“單步跟蹤”法的缺點(diǎn)。

2 案例分析

正確設(shè)計(jì)一個(gè)遞歸算法的前提是分析問(wèn)題、明確具體任務(wù)并給出清晰的遞歸定義。接下來(lái)，筆者通過(guò)兩個(gè)案例來(lái)說(shuō)明遞歸樹在研究遞歸算法并把遞歸算法轉(zhuǎn)換為相應(yīng)的非遞歸算法中的作用。以下算法均采用類C++程序設(shè)計(jì)語(yǔ)言進(jìn)行定義和描述。

2.1 漢諾塔（Tower of Hanoi）問(wèn)題

用狀態(tài)變量（n， A， B， C）表示“把 n 個(gè)盤子從A柱，借助于B柱移動(dòng)到C柱上”。參數(shù)n表示當(dāng)前的盤子數(shù)量；參數(shù)A、B和C分別為柱子的編號(hào)。漢諾塔問(wèn)題的遞歸解法為：

void Hanoi_R（n， A， B， C） {

if （n == 1）

move （A， C）； /* 相當(dāng)于 Hanoi（1， A， B， C） */

else {

Hanoi_R （n-1， A， C， B）；

move （A， C）；

Hanoi_R （n-1， B， A， C）；

}

}

用遞歸樹描述該遞歸算法（以n = 3為例），如圖1所示。

圖1直觀地描述了n（= 3）個(gè)盤子時(shí)的解決方法，其中，遞推動(dòng)作包括3個(gè)步驟，即每個(gè)度為3的結(jié)點(diǎn)下的3個(gè)結(jié)點(diǎn)；遞歸的結(jié)束條件對(duì)應(yīng)n = 1的結(jié)點(diǎn)。

從圖1中可知漢諾塔問(wèn)題的遞歸樹為3叉樹。其中n為1時(shí)表明結(jié)點(diǎn)為葉子，可直接求解，不必再遞歸。如果對(duì)該3叉樹進(jìn)行后根序遍歷（此問(wèn)題只須遍歷葉子結(jié)點(diǎn)）可得到整個(gè)問(wèn)題的解。

為了能區(qū)別同一結(jié)點(diǎn)下的所有子女（Child）的處理次序，把結(jié)點(diǎn)結(jié)構(gòu)改為（n， A， B， C， k），其中k表示該結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的第幾個(gè)子女。這樣，漢諾塔問(wèn)題要解決的問(wèn)題是（3， A， B， C， 1）對(duì)應(yīng)的解，相應(yīng)的非遞歸算法如下：

void Hanoi_I（n， A， B， C） {

StackInitialize S； /* 初始化棧 */

StackElement p =： （n， A， B， C， 1）； S.Push（p）； /* 樹根p入棧 */

while（！S.IsEmpty（ ）） {

S.getTop（p）； /* 取棧頂 */

if（p.n == 1） { /* 1） 若棧頂元素的 n 值為 1，*/

S.Pop（p）； move（p.A， p.C）； /* 出棧并輸出相應(yīng)的解 */

if（p.k == 1） { /* 1.1） 若棧頂元素的 k 值為 1，則 */

p =： （1， p.A， p.C， p.B， 2）； S.Push（p）；/* 其右兄弟（第2步）入棧 */

}

else if（p.k == 2）{ /* 1.2） 若棧頂元素的 k 值為2，則 */

S.getTop（p）；

p =： （p.n-1， p.B， p.A， p.C， 3）； S.Push（p）； /* 其右兄弟（第3步）入棧 */

}

else { /* 1.3） 若棧頂元素的 k 值為3，則 */

/* 1.3.1） 若棧不空且棧頂元素的 k 值為3，向上回溯 */

while（p.k == 3 && ！S.IsEmpty（ ）） S.Pop（p）；

/* 1.3.2） 若棧不空，則k只能為1，此時(shí)其右兄弟（第2步）入棧 */

if（！S.IsEmpty（ ）） {

p =： （1， p.A， p.C， p.B， 2）； S.Push（p）；

}

}

}

else { /* 2） 若棧頂元素的 n 值不為 1，則 */

// 該子問(wèn)題還需要再劃分，把劃分的第1步所對(duì)應(yīng)的結(jié)點(diǎn)入棧

p =： （p.n-1； p.A， p.C， p.B， 1）； S.Push（p）；

}

} /* while */

}

2.2 Ackerman函數(shù)的計(jì)算

Ackerman函數(shù)的定義為

可以用狀態(tài)變量（m，n）表示函數(shù)akm（m， n）的值。由于這是一個(gè)遞歸定義，因此很容易用遞歸方法設(shè)計(jì)出其遞歸解法。

根據(jù)Ackerman函數(shù)的定義，其遞歸程序如下：

int akm_R（int m， int n） {

if（m == 0） return n+1；

else if（n == 0）return akm_R（m-1， 1）；

else return akm_R（m-1， akm_R（m， n-1））；

}

其對(duì)應(yīng)的遞歸樹如圖2所示（以m = 2，n = 1為例），其中虛線框內(nèi)的結(jié)點(diǎn)表示第三種情況（m ≠ 0，n ≠ 0），需要兩次遞歸。

該樹的非遞歸算法如下：

int akm_R（int m， int n） {

StackInitialize S； /* 初始化棧 */

StackElement p =： （m， n）；

S.Push（p）； /* 樹根入棧 */

while（！S.IsEmpty（ ）） {

S.getTop（p）； /* 取棧頂 */

if（p.m > 0 && p.n > 0） { /* 1） 第三種情況，需要兩次入棧 */

S.Push（p.m-1， -1）； /* 1.1） 第1次進(jìn)棧，用 n == -1 表示其值待求 */

S.Push（p.m， p.n-1）； /* 1.2） 第2次進(jìn)棧 */

}

else if（p.m > 0 && p.n == 0） /* 2） 第二種情況，入棧一次 */

S.Push（p.m-1， 1）；

else if（p.m == 0） { /* 3） 第一種情況，直接求解并回歸 */

/* 3.1） 出棧，用p表示出棧元素 */

if（！S.IsEmpty（ ））S.Pop（p）；

/* 3.2） 若p中沒(méi)有待求項(xiàng)（第一種情況），則直接算出結(jié)果并向根部返回 */

if（p.n ！= -1） n = p.n+1；

while（p.n ！= -1 && ！S.IsEmpty（ ）） S.Pop（p）；

/* 3.3） 若p中有待求項(xiàng)，則把結(jié)果賦給待求項(xiàng)，入棧，開始新遞歸 */

if（！S.IsEmpty（ ）） { m = p.m； p.n = n； S.Push（p）； }

}

} /* while */

return n；

}

Ackerman函數(shù)是一個(gè)增長(zhǎng)速度很快的函數(shù)。在硬件為4G內(nèi)存、I3-2120 3.30GHz CPU，軟件為Windows 7（64位）操作系統(tǒng)、DEV C++ 5.9.2環(huán)境下，以m = 4，n = 1為例，非遞歸算法在約90秒左右的時(shí)間里算出結(jié)果為65 533，棧里存儲(chǔ)的最大元素個(gè)數(shù)為1 063 453 415，而遞歸算法因空間資源消耗過(guò)大無(wú)法算出結(jié)果。

3 結(jié) 語(yǔ)

在實(shí)際中，遞歸問(wèn)題是一個(gè)比較常見的問(wèn)題，如n皇后問(wèn)題、迷宮問(wèn)題、二叉樹遍歷等，而遞歸方法是解決遞歸問(wèn)題的一個(gè)基本方法。利用開發(fā)工具（如Visual C++、DEC C++）的調(diào)試功能觀察遞歸算法的運(yùn)行過(guò)程往往有較高的難度，特別是對(duì)于遞歸層數(shù)較高的算法。另外，遞歸算法需要依靠系統(tǒng)提供的遞歸棧來(lái)實(shí)現(xiàn)多次自身調(diào)用，這既耗費(fèi)時(shí)間又耗費(fèi)空間，因此人們常用迭代或棧來(lái)設(shè)計(jì)相應(yīng)的非遞歸算法以提高效率，但是對(duì)于初學(xué)者來(lái)說(shuō)，設(shè)計(jì)非遞歸算法的難度往往較大。

參考文獻(xiàn)：

[1] 張俊. 基于遞歸樹的遞歸調(diào)用分析[J]. 實(shí)驗(yàn)室研究與探索， 2010， 29（3）： 83-87.

[2] 黎遠(yuǎn)松. 基于樹的遞歸算法分析技術(shù)[J]. 四川理工學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2012，25（4）： 50-51.

[3] 周集良. 描述遞歸算法的有效工具： 遞歸樹[J]. 懷化師專學(xué)報(bào)，1999， 18（5）： 41-44.

[4] 張玉華. 模仿法在數(shù)據(jù)結(jié)構(gòu)遞歸算法設(shè)計(jì)中的教學(xué)實(shí)踐[J]. 計(jì)算機(jī)教育， 2016（1）： 134-138.

[5] 殷人昆. 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述）[M]. 2版. 北京： 清華大學(xué)出版社， 2007： 101-102.

（編輯：郭田珍）