Home > misc, study > Tail Recursion in C [一]

Tail Recursion in C [一]

March 27th, 2009 :: ph4nut
Goto comments Leave a comment

看了《写出正确的尾递归代码》一文，对尾递归的作用有了表面上的理解，但是关于编译器如何优化尾递归为一条跳转指令以及对递归堆栈的处理还不是很清楚。所以有了这篇小文，有什么错误的地方还请各位看官指出。

先来看一下在C语言里一个尾递归的例子：

  1. #include <stdio.h>
  2.  
  3. void add( int  n)
  4. {
  5.     printf( " %d\n",n);
  6.     add(n + 1);
  7. }
  8.  
  9. int main()
  10. {
  11.     add(0);
  12.     return 0;
  13. }

编译这段代码：gcc -o  add.exe add.c

如果运行这个程序的话，当n增加到一定值的话，程序就会推出，因为栈空间不够。

再来用gcc的O2选项(这个选项增加了对尾递归的优化)来优化这段代码并运行：gcc -o add.exe add.c  -O2

如果你运行这个程序，你会发现一直打印递增的n,而没有停止。

接下来我们来比较一下没有优化尾递归和优化后的汇编代码。

未优化尾递归的汇编代码：gcc -S add.c

  1.  .file "add.c"
  2.  .section .rdata,"dr"
  3. LC0:
  4.  .ascii " %d\12"
  5.  .text
  6. .globl _add
  7.  .def _add; .scl 2; .type 32; .endef
  8. _add:
  9.  pushl %ebp
  10.  movl %esp, %ebp
  11.  subl $8, %esp
  12.  movl 8(%ebp), %eax
  13.  movl %eax, 4(%esp)
  14.  movl $LC0, (%esp)
  15.  call _printf
  16.  movl 8(%ebp), %eax
  17.  incl %eax
  18.  movl %eax, (%esp)
  19.  call _add  ;注意这里，add函数的调用
  20.  leave
  21.  ret
  22.  .def ___main; .scl 2; .type 32; .endef
  23. .globl _main
  24.  .def _main; .scl 2; .type 32; .endef
  25. _main:
  26.  pushl %ebp
  27.  movl %esp, %ebp
  28.  subl $8, %esp
  29.  andl $-16, %esp
  30.  movl $0, %eax
  31.  addl $15, %eax
  32.  addl $15, %eax
  33.  shrl $4, %eax
  34.  sall $4, %eax
  35.  movl %eax, -4(%ebp)
  36.  movl -4(%ebp), %eax
  37.  call __alloca
  38.  call ___main
  39.  movl $0, (%esp)
  40.  call _add
  41.  movl $0, %eax
  42.  leave
  43.  ret
  44.  .def _printf; .scl 3; .type 32; .endef

优化了尾递归的汇编代码：gcc -O2 add.c

  1.  .file "add.c"
  2.  .section .rdata,"dr"
  3. LC0:
  4.  .ascii " %d\12 "
  5.  .text
  6.  .p2align 4,,15
  7. .globl _add
  8.  .def _add; .scl 2; .type 32; .endef
  9. _add:
  10.  pushl %ebp
  11.  movl %esp, %ebp
  12.  pushl %ebx
  13.  subl $20, %esp
  14.  movl 8(%ebp), %ebx
  15.  .p2align 4,,15
  16. L2:
  17.  movl %ebx, 4(%esp)
  18.  incl %ebx
  19.  movl $LC0, (%esp)
  20.  call _printf
  21.  jmp L2  ;注意这里，尾递归被优化成了一条跳转指令。
  22.  .def ___main; .scl 2; .type 32; .endef
  23.  .p2align 4,,15
  24. .globl _main
  25.  .def _main; .scl 2; .type 32; .endef
  26. _main:
  27.  pushl %ebp
  28.  movl $16, %eax
  29.  movl %esp, %ebp
  30.  subl $8, %esp
  31.  andl $-16, %esp
  32.  call __alloca
  33.  call ___main
  34.  movl $0, (%esp)
  35.  call _add
  36.  
  37. leave
  38.  xorl %eax, %eax
  39.  ret
  40.  .def _printf; .scl 3; .type 32; .endef

从上面两段代码看来，add函数的确有差别，但是重点在于，优化后对堆栈的处理。还是在来看优化后的代码片段（跟上面的一样，只不过我摘取了重点）

  1. _add:
  2.  pushl %ebp  ;标记1
  3.  movl %esp, %ebp
  4.  pushl %ebx
  5.  subl $20, %esp
  6.  movl 8(%ebp), %ebx
  7.  .p2align 4,,15  ;标记2
  8.  
  9. L2:
  10.  movl %ebx, 4(%esp)
  11.  incl %ebx
  12.  movl $LC0, (%esp)
  13.  call _printf
  14.  jmp L2
  15.  .def ___main; .scl 2; .type 32; .endef
  16.  .p2align 4,,15

从标记1 – 标记2，这段代码在add函数递归的过程只执行了一遍，这就说明了，优化后的代码，在堆栈上分配参数的时候，只分配了一次，也就是在第一次调用add函数的时候，现在我们终于明白了尾递归为什么不消耗栈的原因了。同样的，如果在add函数里定义了一些变量（当然要在递归调用的前面），变量在堆栈上也只是分配了一次。

到此，尾递归这个问题也应该告一段落了，但是还有一个问题值得一提，上面的add函数是个无限的递归，永不返回，如果再加一个递归终结的条件，当add函数（也就是最深一层的add函数）返回的时候，它不是向上一层递归地返回，而是直接跳到第一个add调用者（在这个例子应该是main函数）的下一个语句。这个下一篇文章在详细解释吧。

misc, study

  1. jackyz
    March 27th, 2009 at 16:54 | #1
    Reply | Quote

    很有益处的文章。不仅让人知道“尾递归”是什么，还讲明白了它具体是怎么做到的。反过来，对“尾递归”是什么又再有了更深一层的了解。

  2. ph4nut
    March 27th, 2009 at 20:52 | #2
    Reply | Quote

    @jackyz
    尾递归确实需要深一层的了解，特别是在FP领域；刚学Erlang不久，希望能有所收获。

  3. mryufeng
    March 30th, 2009 at 17:25 | #3
    Reply | Quote

    大部分系统都是用jump语句代替call, 同时清除当前的函数调用堆栈，lua是专门一条op_code来做这个事情的。

  4. JGU
    May 8th, 2009 at 21:38 | #4
    Reply | Quote

    ，

  1. No trackbacks yet.