遞迴
更新：2007 年 11 月
遞迴是一種重要的程式設計技巧，可以使函式呼叫其本身。階乘計算就是一個例子。0 的階乘特別定義為 1。大於 0 之整數的 n 個階乘是從範圍 1 到 n 之所有整數的結果。
使用遞迴
以下段落是一個以文字定義的計算階乘的函式。
「如果數字小於零，就加以拒絕。如果數字不是整數，也加以拒絕。如果該數字是零，則它的階乘就是一。如果數字大於零，則將它乘以比該數字小的下一個數字的階乘。」
若要計算任何大於零之數字的階乘，還必須至少計算一個其他數字的階乘。在函式執行目前數字之前，必須呼叫本身以便執行下一個較小的數字。這就是遞迴的範例。
遞迴和重複 (迴圈) 有強烈相關 — 函式可用遞迴或重複而傳回相同的結果。通常一個特定的計算有一種以上的技巧可用，您只要選擇最自然或慣用的方法。
儘管遞迴具有如此效用，仍有可能建立出一個不會傳回結果且不會到達終點的遞迴函式。這樣的遞迴函式會使電腦執行一個無限迴圈。如下範例所示：省略階乘計算的用語描述中第一條規則 (與負數相關的規則)，然後試著計算任何負數的階乘。失敗的原因是計算了 -24 的階乘，而您必須計算 -25 的階乘。為了計算 -25 的階乘，您必須先計算 -26 的階乘，以此類推。顯然地，這永遠也無法停止。
遞迴可能發生的另一個問題是，遞迴函式可以使用所有可用的資源 (像是系統記憶體、堆疊空間等)。遞迴函式每次呼叫本身 (或是呼叫其他呼叫原始函式的函式) 時，它會用掉某些資源。當遞迴函式退出時會釋放這些資源，但有許多層次遞迴的函式則會用掉所有可用的資源。這種情況發生時，就會產生例外狀況。
因此，您一定要小心翼翼地設計遞迴函式。如果您懷疑會產生過度 (無限) 遞迴時，請將函式設計成計算呼叫自己的次數，並且設定呼叫次數的限制。如果函式呼叫自己的次數超過臨界值，函式就會自動退出。重複的最佳極大數值是根據遞迴函式而定。
以下又是階乘函式，這次是以 JScript 程式碼寫成的。使用型別附註，則函式只接受整數。如果傳遞了無效的數字 (小於零的數字)，throw 陳述式就會產生錯誤。另一個情況是，使用遞迴函式計算階乘。遞迴函式接受兩種引數，分別是階乘引數和計數器引數，以便追蹤目前的遞迴層次。如果計數器沒有到達最大遞迴階層，就會傳回原始數字的階乘。
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
本程式的輸出為：
120
7.156945704626378e+118