遞迴是每個工程師都學過、卻常常在細節上翻車的觀念。本文用一個最經典的階乘例子,帶你看清楚遞迴函式在「被搬走之後」會發生什麼事,以及三種因應寫法。
function factorial(n) {
if (n <= 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}
看起來沒問題,但這份程式有一個隱性依賴:函式內部呼叫的是「factorial 這個名字」,而不是「自己這個函式物件」。
var fcopy = factorial; factorial = null; alert(fcopy(3));
這段程式會直接出錯。原因是 fcopy 只是指向原本那個函式物件的「別名」,而函式體內呼叫的 factorial 已經被設成 null,等於自己把自己的呼叫路徑切斷了。這在把函式當回呼傳遞、或做 AOP 包裝時特別容易遇到。
每次進入函式,執行環境都會建立一個特殊的 arguments 物件,而它上面的 callee 屬性正指向「目前執行的函式本身」。
function factorial(n) {
if (n <= 1) {
return 1;
} else {
return arguments.callee(n - 1) * n;
}
}
這樣一來,無論外部名稱怎麼變,遞迴都能找到自己的本尊。不過要注意:callee 在嚴格模式(strict mode)下已被禁用,而且它也會讓引擎無法做某些優化,因此不建議在新專案中使用。
var factorial = function f(n) {
if (n <= 1) {
return 1;
} else {
return f(n - 1) * n;
}
};
這裡沒有任何新技術,只是觀念上的轉換:定義時直接建立一個函式,再把它的參照交給 factorial。關鍵在於函式表達式可以帶一個「內部名稱」f,這個名稱只在函式自身的作用域內可見,外部完全無法存取,也不會被覆寫,因此遞迴永遠穩固。
實務上的建議很清楚:需要遞迴時,優先使用具名函式表達式;只有在維護老舊且無法修改的程式碼時,才退回 arguments.callee。
除了階乘,遞迴也常用在深層複製、DOM 樹或 JSON 樹的走訪、資料結構(樹、圖)的遍歷等場景,把「自己呼叫自己」這條路徑寫得穩健,是寫好這類演算法的基礎。