昨天下午的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语言中也可以编写尾递归的代码，但这依赖于编译器的优化能力。还应慎用！