js-學習篇遞歸調用

js-學習篇遞歸調用

程序調用自身的編程技巧稱為遞歸(recursion)。

階乘

以階乘為例:

function factorial(n) {
if (n == 1) return n;
return n * factorial(n - 1)
}
console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

在《JavaScript專題之函數記憶》中講到過的斐波那契數列也使用了遞歸:

function fibonacci(n){
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)) // 1 1 2 3 5

遞歸條件

從這兩個例子中,我們可以看出:

構成遞歸需具備邊界條件、遞歸前進段和遞歸返回段,當邊界條件不滿足時,遞歸前進,當邊界條件滿足時,遞歸返回。階乘中的 n == 1 和 斐波那契數列中的 n < 2 都是邊界條件。

總結一下遞歸的特點:

  1. 子問題須與原始問題為同樣的事,且更為簡單;
  2. 不能無限制地調用本身,須有個出口,化簡為非遞歸狀況處理。

瞭解這些特點可以幫助我們更好的編寫遞歸函數。

執行上下文棧

在《JavaScript深入之執行上下文棧》中,我們知道:

當執行一個函數的時候,就會創建一個執行上下文,並且壓入執行上下文棧,當函數執行完畢的時候,就會將函數的執行上下文從棧中彈出。

試著對階乘函數分析執行的過程,我們會發現,JavaScript 會不停的創建執行上下文壓入執行上下文棧,對於內存而言,維護這麼多的執行上下文也是一筆不小的開銷吶!那麼,我們該如何優化呢?

答案就是尾調用。

尾調用

尾調用,是指函數內部的最後一個動作是函數調用。該調用的返回值,直接返回給函數。

舉個例子:

// 尾調用 

function f(x){
return g(x);
}

然而

// 非尾調用
function f(x){
return g(x) + 1;
}

並不是尾調用,因為 g(x) 的返回值還需要跟 1 進行計算後,f(x)才會返回值。

兩者又有什麼區別呢?答案就是執行上下文棧的變化不一樣。

為了模擬執行上下文棧的行為,讓我們定義執行上下文棧是一個數組:

 ECStack = [];

我們模擬下第一個尾調用函數執行時的執行上下文棧變化:

// 偽代碼
ECStack.push( functionContext);
ECStack.pop();
ECStack.push( functionContext);
ECStack.pop();

我們再來模擬一下第二個非尾調用函數執行時的執行上下文棧變化:

ECStack.push( functionContext);
ECStack.push( functionContext);
ECStack.pop();
ECStack.pop();

也就說尾調用函數執行時,雖然也調用了一個函數,但是因為原來的的函數執行完畢,執行上下文會被彈出,執行上下文棧中相當於只多壓入了一個執行上下文。然而非尾調用函數,就會創建多個執行上下文壓入執行上下文棧。

函數調用自身,稱為遞歸。如果尾調用自身,就稱為尾遞歸。

所以我們只用把階乘函數改造成一個尾遞歸形式,就可以避免創建那麼多的執行上下文。但是我們該怎麼做呢?

階乘函數優化

我們需要做的就是把所有用到的內部變量改寫成函數的參數,以階乘函數為例:

function factorial(n, res) {
if (n == 1) return res;
return factorial(n - 1, n * res)
}
console.log(factorial(4, 1)) // 24

然而這個很奇怪吶……我們計算 4 的階乘,結果函數要傳入 4 和 1,我就不能只傳入一個 4 嗎?

這個時候就要用到我們在《JavaScript專題之偏函數》中編寫的 partial 函數了:

var newFactorial = partial(factorial, _, 1)
newFactorial(4) // 24

應用

如果你看過 JavaScript 專題系列的文章,你會發現遞歸有著很多的應用。

作為專題系列的第十八篇,我們來盤點下之前的文章中都有哪些涉及到了遞歸:

1.《JavaScript 專題之數組扁平化》:

function flatten(arr) {
return arr.reduce(function(prev, next){
return prev.concat(Array.isArray(next) ? flatten(next) : next)
}, [])
}

2.《JavaScript 專題之深淺拷貝》:

var deepCopy = function(obj) {
if (typeof obj !== 'object') return;
var newObj = obj instanceof Array ? [] : {};
for (var key in obj) {
if (obj.hasOwnProperty(key)) {
newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
}
}
return newObj;
}

3.JavaScript 專題之從零實現 jQuery 的 extend:

// 非完整版本,完整版本請點擊查看具體的文章
function extend() {
...
// 循環遍歷要複製的對象們
for (; i < length; i++) {
// 獲取當前對象
options = arguments[i];
// 要求不能為空 避免extend(a,,b)這種情況
if (options != null) {
for (name in options) {
// 目標屬性值
src = target[name];
// 要複製的對象的屬性值
copy = options[name];
if (deep && copy && typeof copy == 'object') {
// 遞歸調用
target[name] = extend(deep, src, copy);
}
else if (copy !== undefined){
target[name] = copy;
}
}
}
}
...
};

4.《JavaScript 專題之如何判斷兩個對象相等》:

// 非完整版本,完整版本請點擊查看具體的文章
// 屬於間接調用
function eq(a, b, aStack, bStack) {
...
// 更復雜的對象使用 deepEq 函數進行深度比較
return deepEq(a, b, aStack, bStack);
};
function deepEq(a, b, aStack, bStack) {

...
// 數組判斷
if (areArrays) {
length = a.length;
if (length !== b.length) return false;
while (length--) {
if (!eq(a[length], b[length], aStack, bStack)) return false;
}
}
// 對象判斷
else {
var keys = Object.keys(a),
key;
length = keys.length;
if (Object.keys(b).length !== length) return false;
while (length--) {
key = keys[length];
if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack))) return false;
}
}
}

5.《JavaScript 專題之函數柯里化》:

// 非完整版本,完整版本請點擊查看具體的文章
function curry(fn, args) {
length = fn.length;
args = args || [];
return function() {
var _args = args.slice(0),
arg, i;
for (i = 0; i < arguments.length; i++) {
arg = arguments[i];
_args.push(arg);
}
if (_args.length < length) {
return curry.call(this, fn, _args);
}
else {
return fn.apply(this, _args);
}
}
}


分享到:


相關文章: