尾調用優化——記一道面試題的思考

awkj 發布于2019-08-22 17:00 / 2562人閱讀

摘要：如果函數內部還調用函數，那就還有一個的調用幀，依次類推。等同于等同于如果所有函數都是尾調用，那么完全可以做到每次執行時，調用幀只有一項，這將大大節省內存。這就是尾調用優化。尾遞歸函數調用自身，稱為遞歸。

前言

面某東，有一道題目是

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

拿到這個題目，二話沒想就寫了

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

后來回想，后悔死了，這明顯沒這么簡單，每次遞歸調用都會呈指數往調用棧里增加記錄“調用幀“，這樣做，當項比較多，就會出現“棧溢出”的！！！也就是，這個答案是不及格的，正確姿勢應該用尾遞歸優化，”調用幀“保持只有一個。正解也就是：

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

下面來復習一下知識點：尾調用和尾遞歸。PS：更好的方案請繼續往下看。

尾調用

尾調用是指某個函數的最后一步是調用另一個函數。

以下三種情況都不是尾調用：

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

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

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

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

g(x);
return undefined;

函數調用會在內存形成一個“調用記錄”，又稱“調用幀”，保存調用位置和內存變量等信息。如果在函數A的內部調用函數B，那么在A的調用幀上方，還會形成一個B的調用幀。等到B運行結束，將結果返回到A，B的調用幀才會消失。如果函數B內部還調用函數C，那就還有一個C的調用幀，依次類推。所有的調用幀，就形成一個“調用棧”。

尾調用由于是函數的最后一步操作，所有不需要保留外層函數的調用幀，因為調用位置、內部變量等信息都不會再用到了，只要直接用內層函數的調用幀，取代外層函數的調用幀就可以了。

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

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

// 等同于
g(3);

如果所有函數都是尾調用，那么完全可以做到每次執行時，調用幀只有一項，這將大大節省內存。這就是“尾調用優化”。

注意，只有不再用到外層函數的內部變量，內層函數的調用幀才會取代外層函數的調用幀，否則就無法進行“尾調用優化”。

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

尾遞歸

函數調用自身，稱為遞歸。如果尾調用自身，就稱為尾遞歸。遞歸非常耗費內存，因為需要同時保存成百上千調用幀，很容易發生“棧溢出”錯誤。但對于尾遞歸來說，由于只存在一個調用幀，所以永遠不會發生“棧溢出”錯誤。

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

上面最多保存n個調用記錄，復雜度是O(n)。

如果改成尾遞歸，只保留一個調用記錄，復雜度O(1)。

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

下面回到我們的主題，計算Fibonacci數列。

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

上面不使用尾遞歸，項數稍大點就發生”棧溢出“了。

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

上面項數再大都狀態良好。

柯理化改寫

尾遞歸的實現，往往需要改寫遞歸函數，確保最后一步只調用自身。做到這一點的方法，就是把所有用到的內部變量改寫成函數的參數。但是這樣的話就會增加初始入參，比如fibonacci(10, 1, 1)，后面的兩個參數1和1意思不明確，直接用fibonacci(100)才是習慣用法。所以需要在中間預先設置好初始入參，將多個入參轉化成單個入參的形式，叫做函數柯理化。通用方式為：

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);
    }
}

用函數柯理化改寫階乘

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

同樣改寫斐波拉契數列

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改寫

柯理化的過程其實是初始化一些參數的過程，在ES6中，是可以直接函數參數默認賦值的。

用ES6改寫階乘

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

用ES6改寫斐波拉契數列

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極大方便了算法運用！

總結

綜上，這個問題解決的思路是：

尾遞歸+函數柯理化；

尾遞歸+ES6默認賦值；

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

GPU云服務器云服務器尾調用第一道尾隊列長尾詞庫

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/94765.html

[Java] 關于一道面試題的思考

摘要：對于這種會退出的情況，數組顯然不能像鏈表一樣直接斷開，因此采用標記法先生成一個長度為的布爾型數組，用填充。中對整個進行遍歷才能得到此時數組中的數量。文中的速度測試部分，時間是通過簡單的 System.currentTimeMillis() 計算得到的，又由于 Java 的特性，每次測試的結果都不一定相同，對于低數量級的情況有 ± 20 的浮動，對于高數量級的情況有的能有 ± 10...

rozbo 2019-08-15 14:50 評論0 收藏0
對一道【脈脈】上頭條算法面試題的思考

摘要：偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解，簡單的寫了一個網頁開始學的不僅是技術，更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理，鏈接第一個燈，形成環經過測試發現只要從序號開始，如偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

tyheist 2019-08-23 15:18 評論0 收藏0
對一道【脈脈】上頭條算法面試題的思考

摘要：偶然間在脈脈上看到了一道頭條的算法面試題按照題目的理解，簡單的寫了一個網頁開始學的不僅是技術，更是夢想得到了如下效果圖得到如題可以進行開關的示例在最后一個燈特殊處理，鏈接第一個燈，形成環經過測試發現只要從序號開始，如偶然間在脈脈上看到了一道頭條的算法面試題 showImg(https://segmentfault.com/img/bVboxvT?w=1148&h=1080); 按照題...

xuxueli 2019-07-31 10:05 評論0 收藏0
鏈式調用與事件循環--一道JavaScript面試題的思考

摘要：最后畫幾張粗糙的圖，簡單描述一下這個執行的過程因為是鏈式調用，所以在鏈上的都會入棧然后執行，額，執行棧少畫了和。。。前言：昨天在群里討(jin)論(chui)技(niu)術(pi)，有位老鐵發了一道他面的某公司面試題，順手保存了。今早花了一點時間把這題做了出來，發現挺有意思的，決定在今天認真工（hua)作(shui)前，與大家分享我的解題方案和思考過程。題目如下（可以自己先思考一會...

wow_worktile 2019-08-23 15:04 評論0 收藏0
從一道前端面試題談起

摘要：但是題目非要弄成鏈表的形式，說實在的，我真沒有見過前端什么地方還需要用鏈表這種結構的除了面試的時候，所以說這種題目對于實際工作是沒什么用處的，但是腦筋急轉彎的智商題既然這樣出了，我們就來看看怎么解決它吧。今天在知乎上看到一個回答《為什么前端工程師那么難招？》，作者提到說有很多前端工程師甚至連單鏈表翻轉都寫不出來。說實話，來面試的孩子們本來就緊張，你要冷不丁問一句單鏈表翻轉怎么寫，估計...

darkbaby123 2019-08-23 17:53 評論0 收藏0