kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

尾调用 尾递归

尾调用

尾调用大概是这么一种情况:
函数A里面调用了函数B。
函数B执行后,函数A马上返回。
也就是说调用函数B(并返回执行结果)是函数A所做的最后一件事。
相当于执行完函数B后,函数A也就执行完。
因此在执行函数B时,函数A的栈帧其实是已经大部分没用了,可以被修改或覆盖。编译器可以利用这一点进行优化,函数B执行后直接返回到函数A的调用者。

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

尾递归

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

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

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

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

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

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

测试

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

1
2
3
4
5
6
7
8
9
10
11
12
// 递归
int factorial(int n)
{
	if(n <= 2)
	{
		return 1;
	}
	else
	{
		return factorial(n-1) + factorial(n-2);
	}
}

其汇编代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
0100401371    push   %ebp
0200401372    mov    %esp,%ebp
0300401374    push   %ebx
0400401375    sub    $0x14,%esp
0500401378    cmpl   $0x2,0x8(%ebp)
060040137C    jg     0x401385 <factorial+20>
070040137E    mov    $0x1,%eax
0800401383    jmp    0x4013a4 <factorial+51>
0900401385    mov    0x8(%ebp),%eax
1000401388    dec    %eax
1100401389    mov    %eax,(%esp)
120040138C    call   0x401371 <factorial>
1300401391    mov    %eax,%ebx
1400401393    mov    0x8(%ebp),%eax
1500401396    sub    $0x2,%eax
1600401399    mov    %eax,(%esp)
170040139C    call   0x401371 <factorial>
18004013A1    lea    (%ebx,%eax,1),%eax
19004013A4    add    $0x14,%esp
20004013A7    pop    %ebx
21004013A8    leave
22004013A9    ret

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

1
2
3
4
5
6
7
8
9
10
11
int factorial_tail(int n,int acc1,int acc2)
{
  if (n < 2)
  {
      return acc1;
  }
  else
  {
      return factorial_tail(n-1,acc2,acc1+acc2);
  }
}

其汇编代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
0100401381    push   %ebp
0200401382    mov    %esp,%ebp
0300401384    sub    $0x18,%esp
0400401387    cmpl   $0x1,0x8(%ebp)
050040138B    jg     0x401392 <factorial_tail+17>
060040138D    mov    0xc(%ebp),%eax
0700401390    jmp    0x4013b2 <factorial_tail+49>
0800401392    mov    0x10(%ebp),%eax
0900401395    mov    0xc(%ebp),%edx
1000401398    lea    (%edx,%eax,1),%eax
110040139B    mov    0x8(%ebp),%edx
120040139E    dec    %edx
130040139F    mov    %eax,0x8(%esp)
14004013A3    mov    0x10(%ebp),%eax
15004013A6    mov    %eax,0x4(%esp)
16004013AA    mov    %edx,(%esp)
17004013AD    call   0x401381 <factorial_tail>
18004013B2    leave
19004013B3    ret

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