C语言之尾递归

昨天被问到了尾递归及编译器对它的处理相关，一直对它没有研究过，解释得很含糊。
回来查了下，记录如下：

递归有线性递归（普通的递归）和尾递归。
由于尾递归的特殊性，一般的编译器会做些特殊处理。因此，在效率和开销上，比普通递归好。
举个例子，计算n!
1)线性递归：
type recurve(long n)
{
return (n == 1) ? 1 : n * recurve(n - 1);
}
2)尾递归：
type recurve_tail(long n, long result)
{
return (n == 1) ? result : recurve_tail(n - 1, result * n);
}
再封装成1）的形式：
type recurve(long n)
{
return (n == 0) ? 1 : recurve_tail(n, 1);
}

分析：
很容易看出, 普通的线性递归比尾递归更加消耗资源。每次调用都使得调用链条不断加长，系统不得不开辟新的栈进行数据保存和恢复；而尾递归就
不存在这样的问题, 因为他的状态完全由n 和 a 保存，并且，被调用函数返回的值即为要求的值，本函数再没有作用，于是本函数不再保存，直接在本函数堆栈上进行递归调用，
对于特殊情况，甚至可以不使用内存空间，直接在寄存器完成。

编译器如何判断是否尾递归？
返回的值是函数本身，没有其它选择。

看一下上述尾递归函数在gcc 4.3.2-1-1下未进行优化的编译结果：
1 .file "rec .c "
2 .text
3 .globl recurve_tail
4 .type recurve_tail , @function
5 recurve_tail :
6 pushl %ebp
7 movl %esp , %ebp
8 subl $24 , %esp
9 cmpl $1 , 8 (%ebp )
10 je .L2
11 movl 12 (%ebp ), %eax
12 movl %eax , %edx
13 imull 8 (%ebp ), %edx
14 movl 8 (%ebp ), %eax
15 subl $1 , %eax
16 movl %edx , 4 (%esp )
17 movl %eax , (%esp )
18 call recurve_tail
19 movl %eax , -4 (%ebp )
20 jmp .L3
21 .L2 :
22 movl 12 (%ebp ), %eax
23 movl %eax , -4 (%ebp )
24 .L3 :
25 movl -4 (%ebp ), %eax
26 leave
27 ret
28 .size recurve_tail , .-recurve_tail
29 .ident "GCC : (Debian 4 .3 .2 -1 .1 ) 4 .3 .2 "
30 .section .note.GNU -stack ,"",@progbits

未进行优化，与普通递归处理方式相同，新开辟了栈；再看-O3优化结果：

1 .file "rec .c "
2 .text
3 .p2align 4 ,,15
4 .globl recurve_tail
5 .type recurve_tail , @function
6 recurve_tail :
7 pushl %ebp
8 movl %esp , %ebp
9 movl 8 (%ebp ), %edx
10 movl 12 (%ebp ), %eax
11 cmpl $1 , %edx
12 je .L2
13 .p2align 4 ,,7
14 .p2align 3
15 .L5 :
16 imull %edx , %eax
17 subl $1 , %edx
18 cmpl $1 , %edx
19 jne .L5
20 .L2 :
21 popl %ebp
22 ret
23 .size recurve_tail , .-recurve_tail
24 .ident "GCC : (Debian 4 .3 .2 -1 .1 ) 4 .3 .2 "
25 .section .note.GNU -stack ,"",@progbits

此时，正如上面分析，一直在本空间计算，未开辟新栈。