摘要：一個解決的辦法是從算法上解決，把遞歸算法改良成只依賴于少數狀態的迭代算法，然而此事知易行難，線性遞歸還容易，樹狀遞歸就難以轉化了，而且并不是所有遞歸算法都有非遞歸實現。

眾所周知，遞歸函數容易爆棧，究其原因，便是函數調用前需要先將參數、運行狀態壓棧，而遞歸則會導致函數的多次無返回調用，參數、狀態積壓在棧上，最終耗盡棧空間。

一個解決的辦法是從算法上解決，把遞歸算法改良成只依賴于少數狀態的迭代算法，然而此事知易行難，線性遞歸還容易，樹狀遞歸就難以轉化了，而且并不是所有遞歸算法都有非遞歸實現。

在這里，我介紹一種方法，利用CPS變換，把任意遞歸函數改寫成尾調用形式，以continuation鏈的形式，將遞歸占用的棧空間轉移到堆上，避免爆棧的悲劇。
需要注意的是，這種方法并不能降低算法的時間復雜度，若是指望此法縮短運行時間無異于白日做夢

下文先引入尾調用、尾遞歸、CPS等概念，然后介紹Trampoline技法，將尾遞歸轉化為循環形式（無尾調用優化語言的必需品），再以sum、Fibonacci為例子講解CPS變換過程（雖然這兩個例子可以輕易寫成迭代算法，沒必要搞這么復雜，但是最為常見好懂，因此拿來做例子，免得說題目都得說半天），最后講通用的CPS變換法則

看完這篇文章，大家可以去看看Essentials of Programming Languages相關章節，可以有更深的認識

文中代碼皆用JavaScript實現

先來探討下在什么情況下函數調用才需要保存狀態

像Add(1, 2)、MUL(1, 2)這種明顯不需要保存狀態，

像Add(1, MUL(1, 2))這種呢？計算完MUL(1, 2)后需要返回結果接著計算Add，因此計算MUL前需要保存狀態

由此，可以得到一個結論，只有函數調用處于參數位置上，調用后需要返回的函數調用才需要保存狀態，上面的例子中，Add是不需要保存狀態，MUL需要保存

尾調用指的就是，無需返回的函數調用，即函數調用不處于參數位置上，上面的例子中，Add是尾調用，MUL則不是
寫成尾調用形式有助于編譯器對函數調用進行優化，對于有尾調用優化的語言，只要編譯器判斷為尾調用，就不會保存狀態

尾遞歸則是指，寫成尾調用形式的遞歸函數，下面是一例

fact_iter = (x, r) => x == 1 ? 1 : fact_iter(x-1, x*r)

而下面的例子則不是尾遞歸，因為fact_rec(x-1)處于*的第二個參數位置上

fact_rec = x => x == 1 ? 1 : x * fact_rec(x-1)

因為尾遞歸無需返回，結果只跟傳入參數有關，因此只需用少量變量記錄其參數變化，便能輕易改寫成循環形式，因此尾遞歸和循環是等價的，下面把fact_iter改寫成循環：

function fact_loop(x)
{
    var r = 1
    
    while(x >= 1)
    {
        r *= x
        x--;
    }
    
    return r;
}

要解釋CPS，便先要解釋continuation，
continuation是程序控制流的抽象，表示后面將要進行的計算步驟

比如下面這段階乘函數

fact_rec = x => x == 1 ? 1 : x * fact_rec(x-1)

顯然，計算fact_rec(4)之前要先計算fact_rec(3)，計算fact_rec(3)之前要先計算fact_rec(2)，...
于是，可以得到下面的計算鏈：

1 ---> fact_rec(1) ---> fact_rec(2) ---> fact_rec(3) ---> fact_rec(4) ---> print

展開計算鏈后，再從前往后執行，就可以得到最終結果。

對于鏈上的任意一個步驟，在其之前的是歷史步驟，之后的是將要進行的計算，因此之后的都是continuation
比如，對于fact_rec(3)，其continuation是fact_rec(4) ---> print
對于fact(1)，其continuation是fact_rec(2) ---> fact_rec(3) ---> fact_rec(4) ---> print

當然，上面的計算鏈不需要我們手工展開和運行，程序的控制流已經由語法規定好，我們只需要按語法寫好程序，解釋器自動會幫我們分解計算步驟并按部就班地計算

然而，當現有語法無法滿足我們的控制流需求怎么辦？比如我們想從一個函數跳轉至另一個函數的某處執行，語言并沒有提供這樣的跳轉機制，那便需要手工傳遞控制流了。

CPS是一種顯式地把continuation作為對象傳遞的coding風格，以便能更自由地操控程序的控制流

既然是一種風格，自然需要有約定，CPS約定：每個函數都需要有一個參數kont，kont是continuation的簡寫，表示對計算結果的后續處理

比如上面的fact_rec(x)就需要改寫為fact_rec(x, kont)，讀作 “計算出x階乘后，用kont對階乘結果做處理”

kont同樣需要有約定，因為continuation是對某計算階段結果做處理的，因此規定kont為一個單參數輸入，單參數輸出的函數，即kont的類型是a->b

因此，按CPS約定改寫后的fact_rec如下：

fact_rec = (x, kont) => x == 1 ? kont(1) : fact_rec(x-1, res => kont(x*res))

當我們運行fact_rec(4, r=>r)，就可以得到結果24

模擬一下fact_rec(3, r=>r)的執行過程，就會發現，解釋器會先將計算鏈分解展開：

fact_rec(3, r=>r)
fact_rec(2, res => (r=>r)(3*res))
fact_rec(1, res => (res => (r=>r)(3*res))(2*res))
(res => (res => (r=>r)(3*res))(2*res))(1)

當然，這種風格非常反人類，因為內層函數被外層函數的參數分在兩端包裹住，不符合人類的線性思維

我們寫成下面這種符合直覺的形式

1 ---> res => 2*res ---> res => 3*res ---> res => res

鏈上每一個步驟的輸出作為下一步驟的輸入

當解釋器展開成上面的計算鏈后，便開始從左往右的計算，直到運行完所有的計算步驟

需要注意到的是，因為kont承擔了函數后續所有的計算流程，因此不需要返回，所以對kont的調用便是尾調用
當我們把程序中所有的函數都按CPS約定改寫以后，程序中所有的函數調用就都變成了尾調用了，而這正是本文的目的
這個改寫的過程就稱為CPS變換

需要警惕的是，CPS變換并非沒有狀態保存這個過程，它只是把狀態保存到continuation對象中，然后一級一級地往下傳，因此空間復雜度并沒有降低，只是不需要由函數棧幀來承受保存狀態的負擔而已

CPS約定簡約，卻可顯式地控制程序的執行，程序里各種形式的控制流都可以用它來表達（比如協程、循環、選擇等），
所以很多函數式語言的實現都采用了CPS形式，將語句的執行分解成一個小步驟一次執行，
當然，也因為CPS形式過于簡潔，表達起來過于繁瑣，可以看成一種高級的匯編語言

經過CPS變換后，遞歸函數已經轉化成一條長長的continuation鏈

尾調用函數層層嵌套，永不返回，然而在缺乏尾調用優化的語言中，并不知曉函數不會返回，狀態、參數壓棧依舊會發生，因此需要手動強制彈出下一層調用的函數，禁止解釋器的壓棧行為，這就是所謂的Trampoline

因為continuation只接受一個結果參數，然后調用另一個continuation處理結果，因此我們需要顯式地用變量v、kont分別表示上一次的結果、下一個continuation，然后在一個循環里不斷地計算continuation，直到處理完整條continuation鏈，然后返回結果

function trampoline(kont_v)  // kont_v = { kont: ..., v: ... }
{
    while(kont_v.kont)
        kont_v = kont_v.kont(kont_v.v);
    
    return kont_v.v;
}

kont_v.kont是一個bounce，每次執行kont_v.kont(kont_v.v)時，都會根據上次結果計算出本次結果，然后彈出下一級continuation，然后保存在對象{v: ..., kont: ...}里

當然，在bounce中用bind的話，就不需要構造對象顯式保存v了，因為bind會將v保存到閉包中，此時，trampoline變成：

function trampoline(kont)
{
    while(typeof kont == "function")
        kont = kont();
    return kont.val;
}

用bind改寫會更簡潔，然而，因為想要求的值有可能是個function，我們需要在bounce里用對象{val: ...}把結果包裝起來

具體應用可看下面的例子

求和的遞歸實現：

sum = x => { if(x == 0) return 0; else return x + sum(x-1) }

當參數過大，比如sum(4000000)，提示Uncaught RangeError: Maximum call stack size exceeded，爆棧了！

現在，我們通過CPS變換，將上面的函數改寫成尾遞歸形式：

首先，為sum多添加一個參數表示continuation，表示對計算結果進行的后續處理，

sum = (x, kont) => ...

其中，kont是一個單參數函數，形如 res => ...，表示對結果res的后續處理

然后逐情況考慮：

當x == 0時，計算結果直接為0，并將kont應用到結果上,

sum = (x, kont) => { if(x == 0) return kont(0); else ... }

當x != 0時，需要先計算x-1的求和，然后將計算結果與x相加，然后把相加結果輸入kont中，

sum = (x, kont) => { 
       if(x == 0) return kont(0); 
       else return sum( x - 1, res => kont(res + x) ) };
}

好了，現在我們已經完成了sum的CPS變換，大家仔細看看，上面的函數已經是尾遞歸形式啦。

現在還有最后的問題，怎么去調用？比如要算4的求和，sum(4, kont)，這里的kont應該是什么呢？

可以這樣想，當我們計算出結果，后續的處理就是把結果簡單地輸出，因此kont應為res => res

sum(4, res => res)

把上面的代碼復制到Console，運行就能得到結果10

下面我們模擬一下sum(3, res => res)的運作，以對其有個直觀的認識

sum( 3, res => res )
sum( 2, res => ( (res => res)(res+3) ) )
sum( 1, res => ( res => ( (res => res)(res+3) ) )(res+2) ) )
sum( 0, res => ( res => ( res => ( (res => res)(res+3) ) )(res+2) ) )(res+1) )

// 展開continuation鏈
( res => ( res => ( res => ( (res => res)(res+3) ) )(res+2) ) )(res+1) )(0)

// 收縮continuation鏈
( res => ( res => ( (res => res)(res+3) ) )(res+2) )(0+1)
( res => ( (res => res)(res+3) ) )(0+1+2)
(res => res)(0+1+2+3)
6

從上面的展開過程可以看到，sum(x, kont)分為兩個步驟：

展開continuation鏈，尾調用函數層層嵌套，先做的continuation在外層，后做的continuation放內層，這也是CPS反人類的原因，人類思考閱讀都是線性的（從上往下，從左往右），而CPS則是從外到內，而且外層函數和參數包裹著內層，閱讀時還需要眼睛在左右兩端不斷游離

收縮continuation鏈，不斷將外層continuation計算的結果往內層傳

當然，現在運行sum(4000000， res => res)，依然會爆棧，因為js默認并沒有對尾調用做優化，我們需要利用上面的Trampoline技法將其改成循環形式（上文已經提過，尾遞歸和循環等價）

可是等等，上面說的Trampoline技法只針對于收縮continuation鏈過程，可是sum(x, kont)還包括展開過程啊？別擔心，可以看到展開過程也是尾遞歸形式，我們只需稍作修改，就可以將其改成continuation的形式：

( r => sum( x - 1, res => kont(res + x) )(null)

如此便可把continuation鏈的展開和收縮過程統一起來，寫成以下的循環形式：

function trampoline(kont_v)
{
    while(kont_v.kont)
        kont_v = kont_v.kont(kont_v.v);
    
    return kont_v.v;
}

function sum_bounce(x, kont)
{    
    if(x == 0) return {kont: kont, v: 0};
    else return { kont: r => sum_bounce(x - 1, res => {
                                                 return { kont: kont, 
                                                          v: res + x }
                                               } ),
                  v: null };
}

var sum = x => trampoline( sum_bounce(x, res => 
                                            {return { kont: null, 
                                                      v: res } }) )

OK，以上便是改成循環形式的尾遞歸寫法，
把sum(4000000)輸入Console，稍等片刻，便能得到答案8000002000000

當然，用bind的話可以改寫成更簡約的形式：

function trampoline(kont)
{
    while(typeof kont == "function")
        kont = kont();
    return kont.val;
}

function sum_bounce(x, kont)
{    
    if(x == 0) return kont.bind(null, {val: 0});
    else return sum_bounce.bind( null, x - 1, res => kont.bind(null, {val: res.val + x}) );
}

var sum = x => trampoline( sum_bounce(x, res => res) )

也能起到同樣的效果

因為Fibonacci是樹狀遞歸，轉換起來要比線性遞歸的sum麻煩一些，先寫出普通的遞歸算法：

fib = x => x == 0 ? 1 : ( x == 1 ? 1 : fib(x-1) + fib(x-2) )

同樣，當參數過大，比如fib(40000)，就會爆棧

開始做CPS變換，有前面例子鋪墊，下面只講關鍵點

添加kont參數，則fib = (x, kont) => ...

分情況考慮

當x == 0 or 1，fib = (x, kont) => x == 0 ? kont(1) : ( x == 1 ? kont(1) ...

當x != 1 or 1，需要先計算x-1的fib，再計算出x-2的fib，然后將兩個結果相加，然后將kont應用到相加結果上

fib = (x, kont) => 
      x == 0 ? kont(1) : 
      x == 1 ? kont(1) : 
               fib( x - 1, res1 => fib(x - 2, res2 => kont(res1 + res2) ) )

以上便是fib經CPS變換后的尾遞歸形式，可見難點在于kont的轉化，這里需要好好揣摩

最后利用Trampoline技法將尾遞歸轉換成循環形式

function trampoline(kont_v)
{
    while(kont_v.kont)
        kont_v = kont_v.kont(kont_v.v);
    
    return kont_v.v;
}

function fib_bounce(x, kont)
{    
    if(x == 0 || x == 1) return {kont: kont, v: 1};
    else return { 
                  kont: r => fib_bounce( x - 1, 
                                         res1 => 
                                         {
                                            return { 
                                             kont: r => fib_bounce(x - 2,
                                                                   res2 =>
                                                                   { 
                                                                     return  { 
                                                                       kont: kont,
                                                                       v: res1 + res2
                                                                     }
                                                                   }), 
                                             v: null 
                                           }
                                         } ),
                  v: null 
                };
}

var fib = x => trampoline( fib_bounce(x, res => 
                                            {return { kont: null, 
                                                      v: res } }) )

OK，以上便是改成循環形式的尾遞歸寫法，
在console中輸入fib(5)、fib(6)、fib(7)可以驗證其正確性，

當然，當你運行fib(40000)時，發現的確沒有提示爆棧了，但是程序卻卡死了，何也？

正如我在前言說過，這種方法并不會降低樹狀遞歸算法的時間復雜度，只是將占用的棧空間以閉包鏈的形式轉移至堆上，免去爆棧的可能，但是當參數過大時，運行復雜度過高，continuation鏈過長也導致大量內存被占用，因此，優化算法才是王道

當然，用bind的話可以改寫成更簡約的形式：

function trampoline(kont)
{
    while(typeof kont == "function")
        kont = kont();
    return kont.val;
}

fib_bounce = (x, kont) =>
 x == 0 ? kont.bind(null, {val: 1}) : 
 x == 1 ? kont.bind(null, {val: 1}) : 
          fib_bounce.bind( null, x - 1, 
                           res1 => fib_bounce.bind(null, x - 2,
                                                   res2 => kont.bind(null, {val: res1.val + res2.val}) ) )

var fib = x => trampoline( fib_bounce(x, res => res) )

也能起到同樣的效果

對于基本表達式如數字、變量、函數對象、參數是基本表達式的內建函數(如四則運算等)等，不需要進行變換，

若是函數定義，則需要添加一個參數kont，然后對函數體做CPS變換

若是參數位置有函數調用的函數調用，fn(simpleExp1, exp2, ..., expn)，如exp2就是第一個是函數調用的參數
則過程比較復雜，用偽代碼表述如下：(<<...>>內表示表達式， <<...@exp...>表示對exp求值后再代回<<...>>中)：

cpsOfExp(<< fn(simpleExp1, exp2, ..., expn) >>, kont)
= cpsOfExp(exp2, << r2 => @cpsOfExp(<< fn(simpleExp1, r2, ..., expn) >>, kont) >>)

順序表達式的變換亦與上類似

當然這個問題不是這么容易講清楚，首先你需要對你想要變換的語言了如指掌，知道其表達式類型、求值策略等，
JavaScript語法較為繁雜，解釋起來不太方便，
之前我用C++模板寫過一個CPS風格的Lisp解釋器，日后有時間以此為例詳細講講