尾呼叫、最佳化和 ES6 | Linux 中國

簡單的尾呼叫 下載[3]

在編譯器的輸出中，在預期會有一個 呼叫[4] 的地方，你可以看到一個 跳轉[5] 指令，一般情況下你可以發現尾呼叫最佳化（以下簡稱 TCO）。在執行時中，TCO 將會引起呼叫棧的減少。

一個通常認為的錯誤觀念是，尾呼叫必須要 遞迴[6]。實際上並不是這樣的：一個尾呼叫可以被遞迴，比如在上面的 finicky() 中，但是，並不是必須要使用遞迴的。在呼叫點只要函式 F 完成它的呼叫，我們將得到一個單獨的尾呼叫。是否能夠進行最佳化這是一個另外的問題，它取決於你的程式設計環境。

“是的，它總是可以！”，這是我們所希望的最佳答案，它是著名的 Scheme 中的方式，就像是在 SICP[7]上所討論的那樣（順便說一聲，如果你的程式不像“一個魔法師使用你的咒語召喚你的電腦精靈”那般有效，建議你讀一下這本書）。它也是 Lua[8] 的方式。而更重要的是，它是下一個版本的 JavaScript —— ES6 的方式，這個規範清晰地定義了尾的位置[9]，並且明確了最佳化所需要的幾個條件，比如，嚴格樣式[10]。當一個程式語言保證可用 TCO 時，它將支援合理尾呼叫proper tail call。

現在，我們中的一些人不能拋開那些 C 的習慣，心臟出血，等等，而答案是一個更複雜的“有時候”，它將我們帶進了編譯最佳化的領域。我們看一下上面的那個 簡單示例[11]；把我們 上篇文章[12] 的階乘程式重新拿出來：

#include  <stdio.h>
int factorial(int n)
{
    int previous = 0xdeadbeef;
    if (n == 0 || n == 1) {
        return 1;
    }
    previous = factorial(n-1);
    return n * previous;
}
int main(int argc)
{
    int answer = factorial(5);
    printf("%d\n", answer);
}

#include <stdio.h> 
#include <sys/types.h>
#include <unistd.h>
int pidFactorial(int n)
{
    if (1 == n) {
        return getpid(); // tail
    }
    return n * pidFactorial(n-1) * getpid(); // not tail
}
int main(int argc)
{
    int answer = pidFactorial(5);
    printf("%d\n", answer);
}

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int tailPidFactorial(int n, int acc)
{
    if (1 == n) {
        return acc * getpid(); // not tail
    }
    acc = (acc * getpid() * n);
    return tailPidFactorial(n-1, acc); // tail
}
int main(int argc)
{
    int answer = tailPidFactorial(5, 1);
    printf("%d\n", answer);
}