據我所知，進行尾呼叫優化的前提是遞回點應該是函式中的最后一句，并且遞回呼叫的結果應該立即回傳。但為什么？
以下是 TCO 的有效示例：
int factorial(int num) {
if (num == 1 || num == 0)
return 1;
return num * factorial(num - 1);
}
那么，根據規則，下面的代碼也可以優化嗎？為什么不？
#include <stdio.h>
int factorial(int num) {
if (num == 1 || num == 0)
return 1;
int temp = num * factorial(num - 1);
printf("%d", temp);
return temp;
}
我想知道我應該如何向其他人解釋為什么上述規則對于擁有 TCO 是必要的。但不僅僅是簡單地跟隨。
uj5u.com熱心網友回復：
遞回呼叫的結果應立即回傳。但為什么？
那是因為為了優化尾呼叫，您需要將最終的遞回呼叫轉換為簡單的“跳轉”指令。當您這樣做時，您只是“替換”函式引數，然后重新啟動函式。
這只有在您可以“丟棄”當前堆疊幀并再次將其重新用于同一函式時才有可能，可能會覆寫它。如果您需要記住一個值以進行更多計算然后回傳，則不能為遞回呼叫使用相同的堆疊幀（即不能將“呼叫”轉換為“跳轉”），因為它可能會擦除/修改該值你想在回來之前記住。
此外，如果您的函式非常簡單（如您的函式），則可能根本不使用堆疊（可能除了回傳地址）而撰寫它，并且只將資料存盤在暫存器中。即使在這種情況下，如果您需要在回傳之前記住其中一個值，您也不希望跳轉到相同的函式（使用相同的暫存器）。
以下是 TCO 的有效示例：
int factorial(int num) { if (num == 1 || num == 0) return 1; return num * factorial(num - 1); }
這不是有效的 TCO！你在做什么return num * <recursive-call>。遞回呼叫不是函式做的最后一件事，在回傳之前有一個乘法。這和寫一樣：
int factorial(int num) {
if (num == 1 || num == 0)
return 1;
int tmp = factorial(num - 1);
tmp *= num;
return tmp;
}
下面的代碼也可以優化嗎？
不！同樣，那里根本沒有尾呼叫，而且更加明顯。您首先進行遞回呼叫，然后進行其他一些操作（乘法和printf），然后回傳。這不能被編譯器優化為尾呼叫。
另一方面，可以將以下代碼優化為尾呼叫：
int factorial(int n, int x) {
if (n == 1)
return x;
int tmp = factorial(n - 1, n * x);
return tmp;
}
您不必在函式的最后一行直接進行遞回呼叫。重要的是您不要在中間（在遞回呼叫和回傳陳述句之間）進行作業，例如呼叫其他函式或進行額外的計算。
重要提示：請注意，無法執行經典 TCO 的事實并不意味著編譯器將無法以其他方式優化您的代碼。事實上，你的第一個函式非常簡單，當在 x86-64 上使用 GCC 編譯時，至少-O2它只是從遞回轉換為迭代（它基本上變成了一個回圈）。我上面的例子也是如此，編譯器只是不關心 TCO，在這種情況下它看到了更好的優化。
這是在 x86-64 上由 GCC 11 生成的第一個函式的匯編程式轉儲（如果您想使用它，請使用Godbolt 鏈接）。如果您不熟悉 x86：num引數在 中edi，eax用于回傳值。
factorial:
mov eax, 1
cmp edi, 1
jbe .L1
.L2:
mov edx, edi
sub edi, 1
imul eax, edx
cmp edi, 1
jne .L2
.L1:
ret
uj5u.com熱心網友回復：
每次呼叫函式都會創建一個堆疊幀，其中包含通過引數傳遞給該函式的任何資料。如果一個函式呼叫另一個函式（包括它自己），一個新的堆疊幀就會被壓入堆疊中。當一個函式完全完成時，它的幀從堆疊中彈出。
堆疊記憶體是有限的。如果我們嘗試將太多幀壓入堆疊，則會出現堆疊溢位錯誤。
尾呼叫優化發揮作用的地方在于，如果在尾呼叫之后沒有任何作業要做，則識別函式已完成。
考慮一種遞回求和一系列數字的方法。
int sum(int start, int stop) {
if (start == stop) {
return start;
}
else {
return start sum(start 1, stop);
}
}
如果我們呼叫sum(1, 5)遞回看起來像這樣：
sum(1, 5)
1 sum(2, 5)
1 2 sum(3, 5)
1 2 3 sum(4, 5)
1 2 3 4 sum(5, 5)
1 2 3 4 5
必須創建幾個堆疊幀來保存它。
通常，需要構建值的事物的尾呼叫優化涉及傳遞給函式的累加器引數。
int sum_tco(int start, int stop, int acc) {
if (start == stop) {
return start acc;
}
else {
return sum_tco(start 1, stop, start acc);
}
}
現在考慮遞回的樣子：
sum_tco(1, 5, 0)
sum_tco(2, 5, 1 0)
sum_tco(3, 5, 2 1 0)
sum_tco(4, 5, 3 2 0)
sum_tco(5, 5, 5 4 3 2 1 0)
5 4 3 2 1 0
我們不需要知道結果是什么sum(1, 5, 0)或sum(3, 5, 2 1 0)將要知道結果sum(5, 5, 5 4 3 2 1 0)是什么，您的計算機也不需要。
智能編譯器會意識到這一點，并在執行程序中洗掉所有先前的堆疊幀。有了TCO，無論這個函式遞回呼叫自己多少次，它都不會溢位堆疊。
（對堆疊行為的描述已被概括，并不打算在技術上深入，而是為了展示 TCO 的概括概念。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/368920.html
上一篇：實作和定義有什么區別？