Tail-Recursion in C
昨天下午的TOI，向同事简要介绍了Erlang，包括在函数式编程语言中常见（亦常用）的尾递归。例如下面的代码：
factorial(N) -> fac_i(N, 1).
fac_i(1, P) -> P;
fac_i(N, P) -> fac_i (N-1, N*P).
这段貌似递归的代码实际上是一个迭代过程。一直以为尾递归是函数式编程语言特有的，昨天在网上看到，其实许多C编译器在打开优化编译选项时，也是可以消解尾递归的，例如SunStudio或GCC。考虑下面的代码：
static int fac_i (int N, int P) {
return N==1? P: fac_i(N-1, P*N);
}
int factorial (int N) {return fac_i (N, 1);}
我们用cc -O -S test.c，将测试的C文件编译为汇编代码，从中你可以清晰地看到，编译器已经将尾递归解开了：
.CG0.67:
cmpl $4,%esi ;/如果参数N小于4，则跳转到.LU0.68，进行单步迭代
jl .LU0.68
.LP2.74:
movl 12(%ebp),%eax
.CG2.14:
imul %ecx,%eax ;/执行4次连续迭代，尽量避免跳转可能造成的性能损失
decl %ecx
imul %ecx,%eax
decl %ecx
imul %ecx,%eax
decl %ecx
imul %ecx,%eax
decl %ecx
.LU3.71:
cmpl $4,%ecx ;/如果N大于4，跳转回去，继续执行4次连续迭代
jg .CG2.14
.LX2.75:
movl %eax,12(%ebp)
.LE2.76:
cmpl $1,%ecx ;/如果N<=1，则跳转到函数结尾，准备返回
jle .LX0.56
.LU0.68:
movl 12(%ebp),%eax
.LU4.72:
imul %ecx,%eax ;/单步迭代
decl %ecx
cmpl $1,%ecx ;/如果1<N<4，则跳转回去继续执行单步迭代
jg .LU4.72
.LX3.77:
movl %eax,12(%ebp)
我们也可以用gcc -O2 -S test.c，看到类似的结果。
关于尾递归的判断条件，应该是： 对函数自身的递归调用，是函数体执行的最后一步（也就是在尾部）。如果它有返回结果，这个返回值不能再参与任何后续的运算。如果我们将fac_i()改为：
static int fac_i (int N, int P) {
return N==1? P: 1+fac_i(N-1, P*N);
}
我们可以看到汇编代码中，看到下面的结果，
.CG3.15:
subl $8,%esp
movl 12(%ebp),%ecx
imul %eax,%ecx
push %ecx
decl %eax
push %eax
call fac_i ;/递归调用fac_i
addl $16,%esp
incl %eax
fac_i()变为了递归调用。
虽然C语言中也可以编写尾递归的代码，但这依赖于编译器的优化能力。还应慎用！
