js尾遞歸最佳化程式碼分享

在學習資料結構和演算法的時候，我們都知道所有的遞歸都是可以優化成堆疊+循環的。 對於特定的遞歸函數，一般我們都是手動對它們進行最佳化的。 

在學習scala的時候，接觸到尾遞歸的概念。我們只要將遞歸寫成尾遞歸方式，編譯器就會自動幫助我們最佳化。
ps:並不是所有的遞迴都可以改寫成尾遞歸
在js中，尾遞歸通常會被解譯器最佳化。然而，並不是所有的js解釋器都支援尾遞歸最佳化。
對於不支援尾遞歸最佳化的環境，我們需要手動將遞歸最佳化成堆疊+循環。
這裡實作了一個通用的方法，將尾遞歸優化成堆疊+循環。
程式碼摘自阮一峰的《ECMAScript入門》這本書。
具體程式碼如下

<span style="font-family: 微软雅黑, "Microsoft YaHei";">function tco(f) {<br/>    var value;    var active = false;    var accumulated = [];    return function accumulator() {<br/>        accumulated.push(arguments);        if(!active) {<br/>            active = true;            while(accumulated.length) {<br/>                value = f.apply(this, accumulated.shift());<br/>            }<br/>            active = false;            return value;<br/>        }<br/>    };<br/>}var sum = tco(function(x, y) {<br/>    if(y > 0) {        return sum(x + 1, y - 1);<br/>    } else {        return x;<br/>    }<br/>});let res = sum(1, 5)<br/>console.info(res);<br/></span>

這段程式碼非常精妙！

分析
已知，任何遞歸可以寫成循環+棧。
實作將任何尾遞歸轉換成循環+棧執行而不需要針對每個尾遞歸函數寫一個實現版本的思路。
困難在於，任何尾遞歸，通用實作。而不是針對某一個遞歸函數。
重點：

• 堆疊中保存的數據，正是遞歸函數的參數。

• 通用實現，那就必須依賴原來的遞歸函數，循環的終止條件，正是遞歸的結束條件。

• 要將遞歸函數的參數入棧，而不修改原來的遞歸函數，就必須用一個函數代替遞歸函數被調用，從而取得函數入參。

• 遞歸函數的終止條件，每一個遞歸函數都不一樣，但是如果遞歸函數沒有再次調用，說明已達到終止條件。即終止條件和遞歸函數的呼叫有關聯。而遞歸函數每次調用，都會將參數入棧。所以可以根據棧中是否有元素，推論是否達到終止條件。

相關推薦：

JavaScript呼叫堆疊、尾遞歸和手動最佳化的詳細介紹

關於尾遞歸的課程推薦

關於尾遞歸的使用詳解_PHP教學

#

以上是js尾遞歸最佳化程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章！