尾呼叫與尾遞回-有解無憂

本講將對尾呼叫與尾遞回進行介紹：函式的最后一條執行陳述句是呼叫一個函式的形式即為尾呼叫；函式尾呼叫自身則為尾遞回，通過改寫回圈即可輕松寫出尾遞回函式，在語言支持尾呼叫優化的條件下，尾呼叫能節省很大一部分記憶體空間，

什么是尾呼叫

問：何為尾呼叫？
說人話：函式的最后一條執行陳述句是呼叫一個函式，這種形式就稱為尾呼叫，

讓我們看看以下幾個例子，

// 正確的尾呼叫：函式/方法的最后一行是去呼叫function2()這個函式
public int function1(){
    return function2();
}

// 錯誤例子1：呼叫完函式/方法后，又多了賦值操作
public int function1(){
    int x = function2();
    return x;
}

// 錯誤例子2：呼叫完函式后，又多了運算操作
public int function1(){
    return function2() + 1;
}

// 錯誤例子3：f(x)的最后一個動作其實是return null
public void function1(){
    function2();
}

尾呼叫優化

以Java為例，JVM會為每個新創建的執行緒都創建一個堆疊（stack），堆疊是用來存盤堆疊幀（stack frame）的容器；而堆疊幀是用來保存執行緒狀態的容器，其主要包括方法的區域變數表（local variable table），運算元堆疊（operand stack），動態連接（dynamic linking）和方法回傳地址（return address）等資訊，
（注：Java語言目前還不支持尾呼叫優化，但尾呼叫優化的原理是相通的，）

堆疊會對堆疊幀進行壓堆疊和出堆疊操作：每當一個Java方法被執行時都會新創建一個堆疊幀（壓堆疊，push），方法呼叫結束后即被銷毀（出堆疊，pop），

在方法A的內部呼叫方法B，就會在A的堆疊幀上疊加一個B的堆疊幀，在一個活動的執行緒中，只有在堆疊頂的堆疊幀才是有效的，它被稱為當前堆疊幀（Current Stack Frame），這個堆疊幀所關聯的方法則被稱為當前方法（Current Method），只有當方法B運行結束，將結果回傳到A后，B的堆疊幀才會出堆疊，

舉個例子，

public int eat(){
    return 5;
}

public int action(){
    int x = eat();
    return x;
}

public int imitate(){
    int x = action();
    return x;
}

public static void main(String[] args){
    imitate();
}

這段代碼對應的堆疊的狀況則為如下：

首先，在main執行緒呼叫了imitate()方法，便將它的堆疊幀壓入堆疊中，
在imitate()方法里，呼叫了action()方法，由于這不是個尾呼叫，在呼叫完action()方法后仍存在一個運算操作，因此將\(action\)的堆疊幀壓入堆疊中后，JVM認為imitate()方法還沒執行完，便仍然保留著\(imitate\)的堆疊幀，
同理：action()方法里對eat()方法的呼叫也不是尾呼叫，JVM認為在呼叫完eat()方法后，action()方法仍未執行結束，因此保留\(action\)的堆疊幀，并繼續往堆疊中壓入\(eat\)的堆疊幀，
eat()方法執行完后，其對應堆疊幀就會出堆疊；action()方法和imitate()方法在執行完后其對應的堆疊幀也依次出堆疊，

但假如我們對上述示例代碼改寫成如下所示：

public int eat(){
    return 5;
}

public int action(){
    return eat();
}

public int imitate(){
    return action();
}

public static void main(String[] args){
    imitate();
}

那么如果尾呼叫優化生效，堆疊對應的狀態就會為如下：

首先，仍然是將imitate()方法的堆疊幀壓入堆疊中，
在imitate()方法中對action()方法進行了尾呼叫，因此在呼叫action()方法時就意味著imitate()方法執行結束：\(imitate\)堆疊幀出堆疊，\(action\)堆疊幀入堆疊，
同理：\(action\)堆疊幀出堆疊，\(eat\)堆疊幀入堆疊，
最后，eat()方法執行完畢，全流程結束，

我們可以看到，由于尾呼叫是函式的最后一條執行陳述句，無需再保留外層函式的堆疊幀來存盤它的區域變數以及呼叫前地址等資訊，所以堆疊從始至終就只保留著一個堆疊幀，這就是尾呼叫優化(tail call optimization)，節省了很大一部分的記憶體空間，

但上面只是理論上的理想情況，把代碼改寫成尾呼叫的形式只是一個前提條件，堆疊是否真的如我們所愿從始至終只保留著一個堆疊楨還得取決于語言是否支持，例如python就不支持，即使寫成了尾遞回的形式，堆疊該爆還是會爆，

尾遞回

問：何為尾遞回？
說人話：函式尾呼叫自身，這個形式就稱為尾遞回，

在手把手教你寫遞回這篇文章中我們提過，遞回對空間的消耗大，例如計算factorial(1000)，就需要保存1000個堆疊幀，很容易就導致堆疊溢位，

但假如我們將其改為尾遞回，那對于那些支持尾呼叫優化的語言來說，就能做到只保存1個堆疊幀，有效避免了堆疊溢位，

那尾遞回函式要怎么寫呢？

一個比較實用的方法就是先寫出用回圈實作的版本，再把回圈中用到的區域變數都改為函式的引數即可，這樣再進入下一層函式時就不需要再用到上一層函式的環境了，到最后一層時就包含了前面所有層的計算結果，就不要再回傳了，

例如階乘函式，

public int fac(int n) {
    int result = 1;
    for (int index = 1; index <= n; index++)
        result = index * result;
    return result;
}

在這個用回圈實作的版本中，可以看到用到了\(result, index\)這兩個區域變數，那就將其改為函式的引數，并且通過回圈可以看出邊界條件是當index == n時；\(n\)從頭到尾不會變；\(index\)在每次進入下一層回圈時會遞增，\(result\)在每次進入下一層回圈時會有變動，我們把這些改動直接照搬，改寫就非常容易了，

所以用尾遞回實作的版本即為如下：

public int fac(int n, int index, int result) {
    if (index == n)
        return index * result;
    else 
        return fac(n, index + 1, index * result);
}

再舉個例子，斐波那契數列（0, 1, 1, 2, 3, 5, 8, 13...）

其回圈實作版本如下：

public int fibo(int n) {
    int a = 0;
    int b = 1;
    int x = 0;
    for (int index = 0; index < n; index++){
    	x = b;
        b = a + b;
        a = x;
    }
    return a;
}

區域變數有\(a, b, index\)（\(x\)作為\(a, b\)賦值的中間變數，在遞回中可以不需要用到），把這些區域變數放到引數串列，邊界條件為當index == n時；并且，在進入下一層回圈時，\(a\)的值會變為\(b\)，\(b\)的值會變為\(a + b\)，\(index\)的值加1，把這些改動照搬，

public int fibo(int n, int a, int b, int index) {
    if (index == n) 
        return a;
    else 
        return fibo(n, b, a + b, index + 1);
}

參考

https://zhuanlan.zhihu.com/p/130885188
https://www.cnblogs.com/minisculestep/articles/4934947.html
https://zhuanlan.zhihu.com/p/24305359
https://www.cnblogs.com/catch/p/3495450.html

創作不易，點個贊再走叭～

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237920.html

標籤：其他

上一篇：1463. Cherry Pickup II (H)

下一篇：對稱的二叉樹