遞迴

更新: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

社群新增項目

顯示: