六. 遞迴
很多高階語言的都有一項重要的特性－遞迴（recursive call）。所謂遞迴，便是利用程式自己呼叫自己的方式來完成工作。遞迴程式的製作，大都以下列方式來完成：
首先是考慮什麼時候程序不會呼叫自己，亦即考慮boundary的問題。其次便是考慮如何呼叫自己來完成工作，這時必須假想呼叫自己的部份已經完成了它所需完成的工作。當依上述步驟完成了演算法之後，接下來便是檢驗的工作了。檢驗的方式通常是假想輸入不同的輸入值（最好取boundary兩端、及其他罕見的輸入值為主，再取一個正常的輸入值），然後看看是否輸出的答案正確，以及有否造成永久迴路的現象等。前者的錯誤是表示第二個步驟有問題，後者的錯誤，則表示第一個步驟有問題。
並非每種程式語言都有遞迴呼叫的結構，因此有時我們必須將遞迴呼叫結構改成非遞迴呼叫結構。這邊舉一個最常見的例子如下：
題目：試分別寫出漢諾依塔（Tower of Hanoi）問題的recursive和non-recursive algorithm。Tower of Hanoi的問題定義如下：
有三根柱子A,B,C和n個環，n是任意正整數。n個環的直徑都不相等。開始時，柱A上已套好n個環，直徑大的在下，直徑小的在上，由小而大，柱B和柱C是空的。現在要把套在柱A的n個環，搬套到柱B上，但是有兩個條件:
(1)每一次只能從一條柱子的頂端拿走一個環套到另一條柱子的頂端。
(2)一環套到一柱頂端時，此環直徑必須小於柱頂環之直徑。
例如n=3時，搬移的順序為：
A→B, A→C, B→C, A→B, C→A, C→B, A→B
答：
(1) recursive algorithm：
Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
if n<=0 then print("error")
else if n=1 thin print(A,"→",B)
else [call HANOI(A,C,B,n-1);
print(A,"→",B);
call HANOI(C,B,A,n-1)]
end
設計的主要觀念為：
1.將A柱中前n-1個環搬到C柱中暫置。（呼叫自己）
2.將A柱中剩下最大的環搬到B柱中。
3.將C柱中的n-1個環搬到B柱中。（呼叫自己）
(2)將recursive改成non-recursive的做法有很多種。如果已經知道recursive algorithm的話，最正統的方法便是直接將它化成non-recursive的形式。由recursive algorithm化成non-recursive algorithm的方法如下:
1.在程式開頭處標上一個label。
2.在每個呼叫自己的敘述的下一個敘述前，各標上一個label。
3.把每個呼叫自己的敘述代換成一個將目前狀態push到stack的敘述，以及將程式參數改變的敘述，然後跳回程式的開頭。
4.將每個返回敘述變成檢查stack的敘述，只有在stack為空時才能返回，否則必須pop出以前的狀態，然後跳到應返回的位置繼續執行。
上述的方法其實是在模擬程序遞迴呼叫的方式，label的記錄則是要得知其返回位址。因此本題的non-recursive algorithm便可以化成:
Procedure HANOI(A,B,C,n) // 將n個環從A移到B //
step 1: if n<=0 then print("error")
else if n=1 then print(A,"→",B)
else [push(A,B,C,n-1,2);
(A,B,C,n)←(A,C,B,n-1);
goto step 1;
step 2: print(A,"→",B);
push(A,B,C,n-1,3);
(A,B,C,n)←(C,B,A,n-1);
goto step 1;
]
step 3: if stack not empty then
[pop(A,B,C,n,ret_step);
goto ret_step]
相關搜索目錄: 語言
