尾調(diào)用優(yōu)化——記一道面試題的思考

awkj 發(fā)布于2019-08-22 17:00 / 2557人閱讀

摘要：如果函數(shù)內(nèi)部還調(diào)用函數(shù)，那就還有一個(gè)的調(diào)用幀，依次類推。等同于等同于如果所有函數(shù)都是尾調(diào)用，那么完全可以做到每次執(zhí)行時(shí)，調(diào)用幀只有一項(xiàng)，這將大大節(jié)省內(nèi)存。這就是尾調(diào)用優(yōu)化。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。

前言

面某東，有一道題目是

實(shí)現(xiàn)一個(gè)斐波拉契數(shù)列， 已知第一項(xiàng)為0，第二項(xiàng)為1，第三項(xiàng)為1，后一項(xiàng)是前兩項(xiàng)之和，即f(n) = f(n - 1) + f(n -2)。

拿到這個(gè)題目，二話沒(méi)想就寫了

function f(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;
    return f(n - 1) + f(n -2);
}

后來(lái)回想，后悔死了，這明顯沒(méi)這么簡(jiǎn)單，每次遞歸調(diào)用都會(huì)呈指數(shù)往調(diào)用棧里增加記錄“調(diào)用幀“，這樣做，當(dāng)項(xiàng)比較多，就會(huì)出現(xiàn)“棧溢出”的！！！也就是，這個(gè)答案是不及格的，正確姿勢(shì)應(yīng)該用尾遞歸優(yōu)化，”調(diào)用幀“保持只有一個(gè)。正解也就是：

function f(n, prev, next) {
    if(n <= 1) {
        return next;
    }
    return f(n - 1, next, prev + next);
}

下面來(lái)復(fù)習(xí)一下知識(shí)點(diǎn)：尾調(diào)用和尾遞歸。PS：更好的方案請(qǐng)繼續(xù)往下看。

尾調(diào)用

尾調(diào)用是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

以下三種情況都不是尾調(diào)用：

// 情況一
function f(x) {
    let y = g(x);
    return y;
}

// 情況二
function f(x) {
    return g(x) + 1;
}

// 情況三
function f(x) {
    g(x);
}

情況一是調(diào)用函數(shù)g之后，還有賦值操作，所以不屬于尾調(diào)用，即使語(yǔ)義完全一樣。情況二也是屬于調(diào)用后還有操作。情況三等同于：

g(x);
return undefined;

函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)“調(diào)用記錄”，又稱“調(diào)用幀”，保存調(diào)用位置和內(nèi)存變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用幀上方，還會(huì)形成一個(gè)B的調(diào)用幀。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用幀才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用幀，依次類推。所有的調(diào)用幀，就形成一個(gè)“調(diào)用棧”。

尾調(diào)用由于是函數(shù)的最后一步操作，所有不需要保留外層函數(shù)的調(diào)用幀，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，只要直接用內(nèi)層函數(shù)的調(diào)用幀，取代外層函數(shù)的調(diào)用幀就可以了。

function f() {
    let m = 0;
    let n = 2;
    return g(m + n);
}
f();

// 等同于
function f() {
    return g(3);
}
f();

// 等同于
g(3);

如果所有函數(shù)都是尾調(diào)用，那么完全可以做到每次執(zhí)行時(shí)，調(diào)用幀只有一項(xiàng)，這將大大節(jié)省內(nèi)存。這就是“尾調(diào)用優(yōu)化”。

注意，只有不再用到外層函數(shù)的內(nèi)部變量，內(nèi)層函數(shù)的調(diào)用幀才會(huì)取代外層函數(shù)的調(diào)用幀，否則就無(wú)法進(jìn)行“尾調(diào)用優(yōu)化”。

function addOne(a) {
    var one = 1;
    function inner(b) {
        return b + one;
    }
    return inner(a);
}

尾遞歸

函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸。遞歸非常耗費(fèi)內(nèi)存，因?yàn)樾枰瑫r(shí)保存成百上千調(diào)用幀，很容易發(fā)生“棧溢出”錯(cuò)誤。但對(duì)于尾遞歸來(lái)說(shuō)，由于只存在一個(gè)調(diào)用幀，所以永遠(yuǎn)不會(huì)發(fā)生“棧溢出”錯(cuò)誤。

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

上面最多保存n個(gè)調(diào)用記錄，復(fù)雜度是O(n)。

如果改成尾遞歸，只保留一個(gè)調(diào)用記錄，復(fù)雜度O(1)。

function factorial(n, total) {
    if (n === 0) return total;
    return factorial(n - 1, n * total);
}
console.log(factorial(5, 1)); // 120

下面回到我們的主題，計(jì)算Fibonacci數(shù)列。

function fibonacci(n) {
    if(n <= 1) return 1;
    return fibonacci(n -1) + fibonacci(n -2);
}
console.log(fibonacci(10)); // 89
console.log(fibonacci(50)); // stack overflow

上面不使用尾遞歸，項(xiàng)數(shù)稍大點(diǎn)就發(fā)生”棧溢出“了。

function fibonacci(n, prev, next) {
    if(n <= 1) return next;
    return fibonacci(n-1, next, prev + next);
}
console.log(fibonacci(10, 1, 1)); // 89
console.log(fibonacci(100, 1, 1)); // 573147844013817200000
console.log(fibonacci(1000, 1, 1)); // 7.0330367711422765e+208

上面項(xiàng)數(shù)再大都狀態(tài)良好。

柯理化改寫

尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。做到這一點(diǎn)的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。但是這樣的話就會(huì)增加初始入?yún)ⅲ热?b>fibonacci(10, 1, 1)，后面的兩個(gè)參數(shù)1和1意思不明確，直接用fibonacci(100)才是習(xí)慣用法。所以需要在中間預(yù)先設(shè)置好初始入?yún)ⅲ瑢⒍鄠€(gè)入?yún)⑥D(zhuǎn)化成單個(gè)入?yún)⒌男问剑凶龊瘮?shù)柯理化。通用方式為：

function curry(fn) {
    var args = Array.prototype.slice.call(arguments, 1);
    return function () {
        var innerArgs = Array.prototype.slice.call(arguments);
        var finalArgs = innerArgs.concat(args);
        return fn.apply(null, finalArgs);
    }
}

用函數(shù)柯理化改寫階乘

function tailFactorial(n, total) {
    if(n === 1) return total;
    return tailFactorial(n - 1, n * total);
}

var factorial = curry(tailFactorial, 1); 
console.log(factorial(5)); // 120

同樣改寫斐波拉契數(shù)列

function tailFibonacci(n, prev, next) {
    if(n <= 1) return next;
    return tailFibonacci(n - 1, next, prev + next);
}

var fibonacci = curry(fibonacci, 1, 1);
console.log(fibonacci(10)); // 89
console.log(fibonacci(100)); // 573147844013817200000
console.log(fibonacci(1000)); // 7.0330367711422765e+208

ES6改寫

柯理化的過(guò)程其實(shí)是初始化一些參數(shù)的過(guò)程，在ES6中，是可以直接函數(shù)參數(shù)默認(rèn)賦值的。

用ES6改寫階乘

const factorial = (n, total = 1) => {
    if(n === 1) return total;
    return factorial(n - 1, n * total);
}
console.log(factorial(5)); // 120

用ES6改寫斐波拉契數(shù)列

const fibonacci = (n, prev = 1, next = 1) => {
    if(n <= 1) return next;
    return fibonacci(n - 1, next, prev + next);
}
console.log(fibonacci(10)); // 89
console.log(fibonacci(100)); // 573147844013817200000
console.log(fibonacci(1000)); // 7.0330367711422765e+208

ps：用ES6極大方便了算法運(yùn)用！

總結(jié)

綜上，這個(gè)問(wèn)題解決的思路是：

尾遞歸+函數(shù)柯理化；

尾遞歸+ES6默認(rèn)賦值；

算法題永遠(yuǎn)要想到性能問(wèn)題，不能只停留到表面，默哀三秒鐘，[悲傷臉.gif]。