定義

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

階乘

以階乘為例：

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

遞歸條件

構(gòu)成遞歸需具備邊界條件、遞歸前進(jìn)段和遞歸返回段，當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)，當(dāng)邊界條件滿足時(shí)，遞歸返回。階乘中的 n == 1 就是邊界條件。

總結(jié)一下遞歸的特點(diǎn)：

1. 子問題須與原始問題為同樣的事，且更為簡單；
2. 不能無限制地調(diào)用本身，須有個(gè)出口，化簡為非遞歸狀況處理。

了解這些特點(diǎn)可以幫助我們更好的編寫遞歸函數(shù)。

執(zhí)行上下文棧

當(dāng)執(zhí)行一個(gè)函數(shù)的時(shí)候，就會(huì)創(chuàng)建一個(gè)執(zhí)行上下文，并且壓入執(zhí)行上下文棧，當(dāng)函數(shù)執(zhí)行完畢的時(shí)候，就會(huì)將函數(shù)的執(zhí)行上下文從棧中彈出。

試著對(duì)階乘函數(shù)分析執(zhí)行的過程，我們會(huì)發(fā)現(xiàn)，JavaScript 會(huì)不停的創(chuàng)建執(zhí)行上下文壓入執(zhí)行上下文棧，對(duì)于內(nèi)存而言，維護(hù)這么多的執(zhí)行上下文也是一筆不小的開銷吶！那么，我們?cè)撊绾蝺?yōu)化呢？
答案就是尾調(diào)用。

尾調(diào)用

尾調(diào)用，是指函數(shù)內(nèi)部的最后一個(gè)動(dòng)作是函數(shù)調(diào)用。該調(diào)用的返回值，直接返回給函數(shù)。

舉個(gè)例子：

// 尾調(diào)用
function f(x){
    return g(x);
}

然而

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

并不是尾調(diào)用，因?yàn)?g(x) 的返回值還需要跟 1 進(jìn)行計(jì)算后，f(x)才會(huì)返回值。

兩者又有什么區(qū)別呢？答案就是執(zhí)行上下文棧的變化不一樣。

為了模擬執(zhí)行上下文棧的行為，讓我們定義執(zhí)行上下文棧是一個(gè)數(shù)組：

    ECStack = [];

我們模擬下第一個(gè)尾調(diào)用函數(shù)執(zhí)行時(shí)的執(zhí)行上下文棧變化：

// 偽代碼
ECStack.push(<f> functionContext);

ECStack.pop();

ECStack.push(<g> functionContext);

ECStack.pop();

我們?cè)賮砟M一下第二個(gè)非尾調(diào)用函數(shù)執(zhí)行時(shí)的執(zhí)行上下文棧變化：

ECStack.push(<f> functionContext);

ECStack.push(<g> functionContext);

ECStack.pop();

ECStack.pop();

也就說尾調(diào)用函數(shù)執(zhí)行時(shí)，雖然也調(diào)用了一個(gè)函數(shù)，但是因?yàn)樵瓉淼牡暮瘮?shù)執(zhí)行完畢，執(zhí)行上下文會(huì)被彈出，執(zhí)行上下文棧中相當(dāng)于只多壓入了一個(gè)執(zhí)行上下文。然而非尾調(diào)用函數(shù)，就會(huì)創(chuàng)建多個(gè)執(zhí)行上下文壓入執(zhí)行上下文棧。

函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸。

所以我們只用把階乘函數(shù)改造成一個(gè)尾遞歸形式，就可以避免創(chuàng)建那么多的執(zhí)行上下文。但是我們?cè)撛趺醋瞿兀?/p>

階乘函數(shù)優(yōu)化

我們需要做的就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)，以階乘函數(shù)為例：

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

console.log(factorial(4, 1)) // 24

然而這個(gè)很奇怪吶……我們計(jì)算 4 的階乘，結(jié)果函數(shù)要傳入 4 和 1，我就不能只傳入一個(gè) 4 嗎？

這個(gè)時(shí)候就要用到我們?cè)?a target="_blank">《JavaScript專題之偏函數(shù)》中編寫的 partial 函數(shù)了：

var newFactorial = partial(factorial, _, 1)

newFactorial(4) // 24

應(yīng)用

如果你看過 JavaScript 專題系列的文章，你會(huì)發(fā)現(xiàn)遞歸有著很多的應(yīng)用。

作為專題系列的第十八篇，我們來盤點(diǎn)下之前的文章中都有哪些涉及到了遞歸：

1.《JavaScript 專題之?dāng)?shù)組扁平化》：

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 專題之從零實(shí)現(xiàn) jQuery 的 extend：

// 非完整版本，完整版本請(qǐng)點(diǎn)擊查看具體的文章
function extend() {

    ...

    // 循環(huán)遍歷要復(fù)制的對(duì)象們
    for (; i < length; i++) {
        // 獲取當(dāng)前對(duì)象
        options = arguments[i];
        // 要求不能為空 避免extend(a,,b)這種情況
        if (options != null) {
            for (name in options) {
                // 目標(biāo)屬性值
                src = target[name];
                // 要復(fù)制的對(duì)象的屬性值
                copy = options[name];

                if (deep && copy && typeof copy == 'object') {
                    // 遞歸調(diào)用
                    target[name] = extend(deep, src, copy);
                }
                else if (copy !== undefined){
                    target[name] = copy;
                }
            }
        }
    }

    ...

};

4.《JavaScript 專題之如何判斷兩個(gè)對(duì)象相等》：

// 非完整版本，完整版本請(qǐng)點(diǎn)擊查看具體的文章
// 屬于間接調(diào)用
function eq(a, b, aStack, bStack) {

    ...

    // 更復(fù)雜的對(duì)象使用 deepEq 函數(shù)進(jìn)行深度比較
    return deepEq(a, b, aStack, bStack);
};

function deepEq(a, b, aStack, bStack) {

    ...

    // 數(shù)組判斷
    if (areArrays) {

        length = a.length;
        if (length !== b.length) return false;

        while (length--) {
            if (!eq(a[length], b[length], aStack, bStack)) return false;
        }
    }
    // 對(duì)象判斷
    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 專題之函數(shù)柯里化》：

// 非完整版本，完整版本請(qǐng)點(diǎn)擊查看具體的文章
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);
        }
    }
}

寫在最后

遞歸的內(nèi)容遠(yuǎn)不止這些，比如還有漢諾塔、二叉樹遍歷等遞歸場景，本篇就不過多展開，真希望未來能寫個(gè)算法系列。