Contents

很多C/C++猴子可能不常到这个概念,有兴趣可以来这儿的科普下:

http://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8

简单说来尾调用意指函数的最后一件事情是调另一个函数这种形式,刚接触时我从这条说明开始记,印象一直深刻不起来,写的时候也总不太确定自己的代码是否“尾调用”了,更不太明白为何要有“尾调用”这种说法。

所以从形式上去了解大概不是个好办法,真正理解并加以运用的是在某次我了解到尾调用的形式下,由于当前栈上不需要在一次函数调用后继续操作,于是调用另外一个函数时就可以将当前栈销毁掉,从而节省不必要的栈开销(push、pop、ret、内存等)。

对我来说,知道这种形式的理由对于编写相关代码很有帮助。

第一次接触这个概念是在两年前刚刚了解Erlang的时候,递归在这类函数式语言里也要承担起loop的工作,基本上无处不递归。

而在这种情况下,函数是否“尾调用”就变得比较重要,尤其是循环量较大的时候。

尾递归是尾调用的一种特殊形式,可以看作是“尾调用”的函数刚好在调自己时的一种称呼吧。

后来很自然开始好奇C++是否也做相同的事情,但编译器是个黑盒,如何测试这个问题呢?

一种简单的办法就是把一个比较大的循环(10W+)按尾调用方式改下,运行看看堆栈会不会爆掉。

进一步的,可以看看汇编后的指令是否已经把栈优化掉了。

先来看看普通的 1+2+3+…+n 的程序:

int sum1toN(int n)
{
        if (n == 0) return 0;
        int left = sum1toN(n-1);
        return n+left;
}

int main()
{
        int sum = sum1toN(100);
        printf("%d\n", sum);
        return 0;
}

编译:g++ xxx.cpp -o xxx

gdb查看汇编代码:

(gdb) disassemble main
Dump of assembler code for function main:
   0x000000000040063c <+0>:	push   %rbp
   0x000000000040063d <+1>:	mov    %rsp,%rbp
   0x0000000000400640 <+4>:	sub    $0x10,%rsp
   0x0000000000400644 <+8>:	mov    $0x0,%esi
   0x0000000000400649 <+13>:	mov    $0x64,%edi
   0x000000000040064e <+18>:	callq  0x400612 <_Z10sum1toN_v2ii>
   0x0000000000400653 <+23>:	mov    %eax,-0x4(%rbp)
   0x0000000000400656 <+26>:	mov    -0x4(%rbp),%eax
   0x0000000000400659 <+29>:	mov    %eax,%esi
   0x000000000040065b <+31>:	mov    $0x40077c,%edi
   0x0000000000400660 <+36>:	mov    $0x0,%eax
   0x0000000000400665 <+41>:	callq  0x400488 <printf@plt>
   0x000000000040066a <+46>:	mov    $0x0,%eax
   0x000000000040066f <+51>:	leaveq 
   0x0000000000400670 <+52>:	retq   
End of assembler dump.

(gdb) disassemble sum1toN
Dump of assembler code for function _Z7sum1toNi:
   0x00000000004005cb <+0>:	push   %rbp
   0x00000000004005cc <+1>:	mov    %rsp,%rbp
   0x00000000004005cf <+4>:	sub    $0x20,%rsp
   0x00000000004005d3 <+8>:	mov    %edi,-0x14(%rbp)
   0x00000000004005d6 <+11>:	cmpl   $0x0,-0x14(%rbp)
   0x00000000004005da <+15>:	jne    0x4005e3 <_Z7sum1toNi+24>
   0x00000000004005dc <+17>:	mov    $0x0,%eax
   0x00000000004005e1 <+22>:	jmp    0x4005fc <_Z7sum1toNi+49>
   0x00000000004005e3 <+24>:	mov    -0x14(%rbp),%eax
   0x00000000004005e6 <+27>:	sub    $0x1,%eax
   0x00000000004005e9 <+30>:	mov    %eax,%edi
   0x00000000004005eb <+32>:	callq  0x4005cb <_Z7sum1toNi>
   0x00000000004005f0 <+37>:	mov    %eax,-0x4(%rbp)
   0x00000000004005f3 <+40>:	mov    -0x4(%rbp),%eax
   0x00000000004005f6 <+43>:	mov    -0x14(%rbp),%edx
   0x00000000004005f9 <+46>:	lea    (%rdx,%rax,1),%eax
   0x00000000004005fc <+49>:	leaveq 
   0x00000000004005fd <+50>:	retq   
End of assembler dump.

可以明显看到0x00000000004005eb处发生了递归调用,符合预期。但是我们知道一般发布的版本都会打开优化开关,所以为了符合实际应用情况,也要在打开优化开关下进行测试:

编译:g++ -O2 xxx.cpp -o xxx

(gdb) disassemble sum1toN
Dump of assembler code for function _Z7sum1toNi:
   0x00000000004005b0 <+0>:	xor    %eax,%eax
   0x00000000004005b2 <+2>:	test   %edi,%edi
   0x00000000004005b4 <+4>:	je     0x4005c7 <_Z7sum1toNi+23>
   0x00000000004005b6 <+6>:	nopw   %cs:0x0(%rax,%rax,1)
   0x00000000004005c0 <+16>:	add    %edi,%eax
   0x00000000004005c2 <+18>:	sub    $0x1,%edi
   0x00000000004005c5 <+21>:	jne    0x4005c0 <_Z7sum1toNi+16>
   0x00000000004005c7 <+23>:	repz retq 
End of assembler dump.

出人意料的是,这种刻意偏离尾调用的写法在O2下也被很好的优化了,产生了和循环相当的代码。

再来看尾递归写法及其汇编:

int sum1toN_v2(int n, int sum)
{
        if (n == 0) return sum;
        return sum1toN_v2(n-1, sum+n);
}

编译:g++ xxx.cpp -o xxx

(gdb) disassemble sum1toN_v2
Dump of assembler code for function _Z10sum1toN_v2ii:
   0x00000000004005fe <+0>:	push   %rbp
   0x00000000004005ff <+1>:	mov    %rsp,%rbp
   0x0000000000400602 <+4>:	sub    $0x10,%rsp
   0x0000000000400606 <+8>:	mov    %edi,-0x4(%rbp)
   0x0000000000400609 <+11>:	mov    %esi,-0x8(%rbp)
   0x000000000040060c <+14>:	cmpl   $0x0,-0x4(%rbp)
   0x0000000000400610 <+18>:	jne    0x400617 <_Z10sum1toN_v2ii+25>
   0x0000000000400612 <+20>:	mov    -0x8(%rbp),%eax
   0x0000000000400615 <+23>:	jmp    0x40062e <_Z10sum1toN_v2ii+48>
   0x0000000000400617 <+25>:	mov    -0x4(%rbp),%eax
   0x000000000040061a <+28>:	mov    -0x8(%rbp),%edx
   0x000000000040061d <+31>:	add    %eax,%edx
   0x000000000040061f <+33>:	mov    -0x4(%rbp),%eax
   0x0000000000400622 <+36>:	sub    $0x1,%eax
   0x0000000000400625 <+39>:	mov    %edx,%esi
   0x0000000000400627 <+41>:	mov    %eax,%edi
   0x0000000000400629 <+43>:	callq  0x4005fe <_Z10sum1toN_v2ii>
   0x000000000040062e <+48>:	leaveq 
   0x000000000040062f <+49>:	retq   
End of assembler dump.

编译:g++ -O2 xxx.cpp -o xxx

(gdb) disassemble sum1toN_v2
Dump of assembler code for function _Z10sum1toN_v2ii:
   0x00000000004005f0 <+0>:	test   %edi,%edi
   0x00000000004005f2 <+2>:	mov    %esi,%eax
   0x00000000004005f4 <+4>:	je     0x400607 <_Z10sum1toN_v2ii+23>
   0x00000000004005f6 <+6>:	nopw   %cs:0x0(%rax,%rax,1)
   0x0000000000400600 <+16>:	add    %edi,%eax
   0x0000000000400602 <+18>:	sub    $0x1,%edi
   0x0000000000400605 <+21>:	jne    0x400600 <_Z10sum1toN_v2ii+16>
   0x0000000000400607 <+23>:	repz retq 
End of assembler dump.

可以看出即便是“尾调用”,在不打开优化开关的默认情况下也是没有作针对性优化的,即这种写法实际上和前面的常规写法得到几乎一样的结果。

由此可见,在C++中“尾调用”应该不是一项由语言本身去规范的行为,而是属于一种“编译器优化”,只有足够好的编译器才能产生令人满意的效果。另一方面,可能也你从来不会在一些C++权威的书籍里看到这个词,C++论坛也很少看到有人讨论它,侧面说明了它不是一项语言标准。

因为C++中支持“循环”,什么情况下非得要把循环写成递归的形式值得深入思考,能够被“尾递归”化的代码通常也能用循环简单的解决。从我个人的使用来说,很多时候递归是一种思路,写成递归式可以很清晰的将这种思路表达出来。比如一个关于字符串对数字和字符进行分组(分组后相对位置关系不变)的栗子:

void ReOrderStr(char* str)
{
	if (!str || !*str) return;
	char* begin = str;
	while (isdigit(*str)) ++str;
	char* mid = str;
	if (!*mid) return;
	while (isalpha(*str)) ++str;
	if (mid-begin > 0)
	{
		std::rotate(begin, mid, str);
	}
	ReOrderStr(begin+(str-mid));
}

// case: "23dsfaa2421b435413dsd" => "dsfaabdsd232421435413"

虽然写成循环也很容易,但却不是最佳选择,这种时候像尾递归优化之类的特性就能派上用场。

就算编译器能够将部分非尾调用代码优化,但也需要明白,编译器的优化能力是有限的,不好的写法和好的写法可能只是一点点区别,但是导致的结果却大相径庭:

int sum1toN(int n)
{
        if (n == 0) return 0;
        int left = sum1toN(n-1);
        printf("%d ", left);
        return n+left;
}

编译:g++ -O2 xxx.cpp -o xxx

(gdb) disassemble sum1toN
Dump of assembler code for function _Z7sum1toNi:
   0x00000000004005f0 <+0>:	mov    %rbx,-0x10(%rsp)
   0x00000000004005f5 <+5>:	mov    %rbp,-0x8(%rsp)
   0x00000000004005fa <+10>:	xor    %eax,%eax
   0x00000000004005fc <+12>:	sub    $0x18,%rsp
   0x0000000000400600 <+16>:	test   %edi,%edi
   0x0000000000400602 <+18>:	mov    %edi,%ebx
   0x0000000000400604 <+20>:	je     0x400622 <_Z7sum1toNi+50>
   0x0000000000400606 <+22>:	lea    -0x1(%rbx),%edi
   0x0000000000400609 <+25>:	callq  0x4005f0 <_Z7sum1toNi>
   0x000000000040060e <+30>:	mov    $0x400768,%edi
   0x0000000000400613 <+35>:	mov    %eax,%ebp
   0x0000000000400615 <+37>:	mov    %eax,%esi
   0x0000000000400617 <+39>:	xor    %eax,%eax
   0x0000000000400619 <+41>:	callq  0x400488 <printf@plt>
   0x000000000040061e <+46>:	lea    0x0(%rbp,%rbx,1),%eax
   0x0000000000400622 <+50>:	mov    0x8(%rsp),%rbx
   0x0000000000400627 <+55>:	mov    0x10(%rsp),%rbp
   0x000000000040062c <+60>:	add    $0x18,%rsp
   0x0000000000400630 <+64>:	retq   
End of assembler dump.

当函数调用后,需要执行像printf这种复杂操作时,编译器就没有办法提供优化了。

最后我来试了间接递归的情况,证明就算是间接递归,只要是“尾调用”的,还是可以把call优化成jnz之类的指令去完成。

保险起见,另外看了几篇关于C++尾调用的讨论,结论基本上差不多吧。

Which, if any, C++ compilers do tail-recursion optimization?
Tail recursion in C++
Tail call optimisation in C++

Contents