尾递归堆栈溢出

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

可以是： - 可以增加堆栈大小或 - 不要使用递归，而是使用某种循环。