递归与循环

一直听说“递归的效率不如循环”，“递归会爆栈”等等说法。想这这里深入分析下递归与非递归的区别。
先看看下面的例子代码以及对应的汇编代码。

int f(int n)
{   
    if(n>0)return 1+f(n-1);
    return 0;
}

int main()
{
    return f(8192*1024);
}

   0x0000000100000f50 <+0>: push   %rbp
   0x0000000100000f51 <+1>: mov    %rsp,%rbp
   0x0000000100000f54 <+4>: sub    $0x10,%rsp
   0x0000000100000f58 <+8>: mov    %edi,-0x8(%rbp)
   0x0000000100000f5b <+11>:    cmpl   $0x0,-0x8(%rbp)
   0x0000000100000f5f <+15>:    jle    0x100000f7d <f+45>
   0x0000000100000f65 <+21>:    mov    -0x8(%rbp),%eax
   0x0000000100000f68 <+24>:    sub    $0x1,%eax
   0x0000000100000f6b <+27>:    mov    %eax,%edi
   0x0000000100000f6d <+29>:    callq  0x100000f50 <f>
   0x0000000100000f72 <+34>:    add    $0x1,%eax
   0x0000000100000f75 <+37>:    mov    %eax,-0x4(%rbp)
   0x0000000100000f78 <+40>:    jmpq   0x100000f84 <f+52>
   0x0000000100000f7d <+45>:    movl   $0x0,-0x4(%rbp)
   0x0000000100000f84 <+52>:    mov    -0x4(%rbp),%eax
   0x0000000100000f87 <+55>:    add    $0x10,%rsp
   0x0000000100000f8b <+59>:    pop    %rbp
   0x0000000100000f8c <+60>:    retq 

我机器本身的默认栈大小为8192kB(可以通过ulimit -a查看)，通过gdb调试，然后查看n为多少的时候崩溃。
Thread 2 received signal SIGSEGV, Segmentation fault.
0x0000000100000f6d in f (n=8126506) at t1.c:4
4 return 1+f(n-1);
在n为8126506时收到段错误的信号，系统杀掉进程。81921024 - 8126506 = 262102，就是说当递归进行到262102次时，堆栈溢出。
在来看看每次调用函数的开销，push %rbp，以及sub $0x10,%rsp，还有隐含的call指令会把pc指针压入栈中，这3个部分的栈增大的大小为32(8+16+8)。递归的次数26210232 = 8387264。这个就是几乎等于系统栈限制的大小了。
这个例子中，可以简单通过一个循环来解决递归的问题。有些需要用用户栈来模拟递归调用的情况，从这个例子中也可以看出，用户栈模拟也会好于递归的调用结果，因为rbp等寄存器不用保存，以及call指令对应的pc指针压栈的操作也减少了，用户栈占用大小比递归时栈的大小也要小很多。
当然递归时，如果优化形成尾递归，也会对缓解栈溢出的风险。上述代码实际就是尾递归，当使用O1优化时，形成的汇编如下

100000f90:  55  pushq   %rbp
100000f91:  48 89 e5    movq    %rsp, %rbp
100000f94:  31 c0   xorl    %eax, %eax
100000f96:  85 ff   testl   %edi, %edi
100000f98:  0f 49 c7    cmovnsl %edi, %eax
100000f9b:  5d  popq    %rbp
100000f9c:  c3  retq
100000f9d:  0f 1f 00    nopl    (%rax)

可以看出编译器优化掉了递归调用，这里直接改成一个简单的条件赋值操作。