尾遞歸堆棧溢出

Question

據我所知，尾遞歸函數在最後一步調用自己（如return語句），但是，函數的第一個實例不會終止，直到所有其他實例都終止，因此在達到多個實例後我們會發生堆棧溢出。鑑於遞歸是最後一步，有什麼辦法在下一個實例期間或之前終止前一個實例嗎？如果一個實例的唯一目的是調用下一個實例，那麼沒有理由將它存放在內存中，對吧？

Answer 1

是的，一些編譯器會優化尾遞歸，因此它不需要額外的堆棧空間。例如，讓我們看一下這個示例的C函數：

int braindeadrecursion(int n) 
{ 
    if (n == 0) 
    return 1; 

    return braindeadrecursion(n - 1); 
} 

這個函數很簡單;它只是返回1.如果沒有優化，鐺產生我的機器上的代碼看起來像這樣：

_braindeadrecursion: 
00 pushq %rbp 
01 movq %rsp,%rbp 
04 subq $0x10,%rsp 
08 movl %edi,0xf8(%rbp) 
0b movl 0xf8(%rbp),%eax 
0e cmpl $_braindeadrecursion,%eax 
11 jne 0x0000001c 
13 movl $0x00000001,0xfc(%rbp) 
1a jmp 0x0000002e 
1c movl 0xf8(%rbp),%eax 
1f subl $0x01,%eax 
22 movl %eax,%edi 
24 callq _braindeadrecursion 
29 movl %eax,%ecx 
2b movl %ecx,0xfc(%rbp) 
2e movl 0xfc(%rbp),%eax 
31 addq $0x10,%rsp 
35 popq %rbp 
36 ret 

正如你所看到的，遞歸調用是在那裏0X24。現在，讓我們嘗試更高的優化：

_braindeadrecursion: 
00 pushq %rbp 
01 movq %rsp,%rbp 
04 movl $0x00000001,%eax 
09 popq %rbp 
0a ret 

現在，看看那個 - 沒有更多的遞歸！這個例子非常簡單，但優化仍然可以發生在更復雜的尾遞歸情況下。

Answer 2

可以是： - 可以增加堆棧大小或 - 不要使用遞歸，而是使用某種循環。