漫谈递归:从汇编看尾递归的优化

尾递归的编译器优化
服务器君一共花费了358.841 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

对于尾递归,很多人的理解仅局限于它是递归和尾调用的一个合体,比普通递归效率高。至于效率为什么高,高在哪,可能没有深究过。 

尾调用

要说尾递归,得先说尾调用。我理解的尾调用大概是这么一种情况:

  1. 函数A里面调用了函数B。
  2. 函数B执行后,函数A马上返回。
  3. 也就是说调用函数B(并返回执行结果)是函数A所做的最后一件事。
  4. 相当于执行完函数B后,函数A也就执行完。

因此在执行函数B时,函数A的栈帧其实是已经大部分没用了,可以被修改或覆盖。编译器可以利用这一点进行优化,函数B执行后直接返回到函数A的调用者。 

这里有一点需要注意:它是来自于编译器的优化。 这一点点的优化对于普通的尾调用来说可能意义不大,但是对于尾递归来说就很重要了。 

尾递归

尾递归是一种基于尾调用形式的递归,相当于前面说的函数B就是函数A本身。 

普通递归会存在的一些问题是,每递归一层就会消耗一定的栈空间,递归过深还可能导致栈溢出,同时又是函数调用,免不了push来pop去的,消耗时间。 

采用尾调用的形式来实现递归,即尾递归,理论上可以解决普通递归的存在的问题。因为下一层递归所用的栈帧可以与上一层有重叠(利用jmp来实现),局部变量可重复利用,不需要额外消耗栈空间,也没有push和pop。 

再次提一下,它的实际效果是来自于编译器的优化(目前的理解)。在使用尾递归的情况下,编译器觉得合适就会将递归调用优化成循环。目前大多数编译器都是支持尾递归优化的。有一些语言甚至十分依赖于尾递归(尾调用),比如erlang或其他函数式语言(传说它们为了更好的处理continuation-passing style)。 

假如不存在优化,大家真刀真枪进行函数调用,那尾递归是毫无优势可言的,甚至还有缺点——代码写起来不直观。 

现代编译器的优化能力很强悍,很多情况下编译器优化起来毫不手软(于是有了volatile)。但有时编译器又很傲娇,你需要主动给它一点信号,它才肯优化。尾递归就相当于传递一个信号给编译器,尽情优化我吧! 

测试

为了验证尾递归优化,可以写个小程序进行测试。在VS2010下将使用/O1或以上的优化选项,一般就会尾递归优化。Gcc3.2.2(这版本好旧)下一般需要使用-O2优化选项。

先看看普通递归:

// 递归
int factorial(int n)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        return factorial(n-1) + factorial(n-2);
    }
}

其汇编代码:

00401371	push   %ebp
00401372	mov    %esp,%ebp
00401374	push   %ebx
00401375	sub    $0x14,%esp
00401378	cmpl   $0x2,0x8(%ebp)
0040137C	jg     0x401385 <factorial+20>
0040137E	mov    $0x1,%eax
00401383	jmp    0x4013a4 <factorial+51>
00401385	mov    0x8(%ebp),%eax
00401388	dec    %eax
00401389	mov    %eax,(%esp)
0040138C	call   0x401371 <factorial>
00401391	mov    %eax,%ebx
00401393	mov    0x8(%ebp),%eax
00401396	sub    $0x2,%eax
00401399	mov    %eax,(%esp)
0040139C	call   0x401371 <factorial>
004013A1	lea    (%ebx,%eax,1),%eax
004013A4	add    $0x14,%esp
004013A7	pop    %ebx
004013A8	leave
004013A9	ret

在0040138C,0040139C这些位置,我们看到递归仍然是使用call指令,那么尾递归在汇编角度是怎么处理的呢?

尾递归:

int factorial_tail(int n,int acc1,int acc2)
{
    if (n < 2)
    {
        return acc1;
    }
    else
    {
        return factorial_tail(n-1,acc2,acc1+acc2);
    }
}

其汇编代码:

00401381	push   %ebp
00401382	mov    %esp,%ebp
00401384	sub    $0x18,%esp
00401387	cmpl   $0x1,0x8(%ebp)
0040138B	jg     0x401392 <factorial_tail+17>
0040138D	mov    0xc(%ebp),%eax
00401390	jmp    0x4013b2 <factorial_tail+49>
00401392	mov    0x10(%ebp),%eax
00401395	mov    0xc(%ebp),%edx
00401398	lea    (%edx,%eax,1),%eax
0040139B	mov    0x8(%ebp),%edx
0040139E	dec    %edx
0040139F	mov    %eax,0x8(%esp)
004013A3	mov    0x10(%ebp),%eax
004013A6	mov    %eax,0x4(%esp)
004013AA	mov    %edx,(%esp)
004013AD	call   0x401381 <factorial_tail>
004013B2	leave
004013B3	ret

在00401390位置上,尾递归是直接使用jmp实现循环跳转。

如何查看C语言程序的汇编?可以看看这篇单独的文章:如何在Code::Blocks下查看程序的汇编代码

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2336,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2336

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《UNIX环境高级编程(第2版)》 史蒂文斯 (作者), 拉戈 (作者), 尤晋元 (译者), 张亚英 (译者), 戚正伟 (译者)

《UNIX环境高级编程(第2版)》是被誉为UNIX编程“圣经”的Advanced Programming in the UNIX Environment一书的更新版。在本书第1版出版后的十几年中,UNIX行业已经有了巨大的变化,特别是影响UNIX编程接口的有关标准变化很大。本书在保持了前一版的风格的基础上,根据最新的标准对内容进行了修订和增补,反映了最新的技术发展。书中除了介绍UNIX文件和目录、标准I/O库、系统数据文件和信息、进程环境、进程控制、进程关系、信号、线程、线程控制、守护进程、各种I/O、进程间通信、网络IPC、伪终端等方面的内容,还在此基础上介绍了多个应用示例,包括如何创建数据库函数库以及如何与网络打印机通信等。

更多计算机宝库...