递归替换：尾递归

来自HNUlanwei的CSDN：http://blog.csdn.net/u010911350

 

递归在很多时候被视为洪水猛兽。它的名声狼籍，好像永远和低效联系在一起。 
其实，对一些如树的递归结构，递归算法是又自然又好用。 
如果看看一些用来代替递归的技术，（汉诺塔的迭代算法不去说它，那是真正的算法的革命，除了佩服没啥好说的），一般来说只不过是自己模拟堆栈，编起来费劲，读起来费劲，维护起来更费劲。而模拟堆栈的效果，相比于简单的递归，好处在哪里呢？ 
1。不使用进程堆栈，不会耗尽堆栈空间（虽然可能耗尽堆空间） 
2。可以有选择地把真正有用的东西压栈，而不用什么pc, sp, 所有的局部变量都压栈。这样节省了一些内存（不过，仍然在一个数量级，递归是O(N)，模拟递归仍然是O(N))。 不过这也不绝对，编译器的优化可以识别一些不需要保存的局部变量的。（这叫变量生存期分析） 


那么这样做又没有坏处呢？除了上面的代码复杂度的问题（我想很多搞嵌入式系统，实时系统的C高手都对此不屑一顾），还有一个效率上的缺点： 
模拟的递归使用堆空间，它的new/delete都比直接在堆栈上分配空间慢得多。而且很容易产生内存碎片。 
所以说，模拟堆栈只不过是牺牲了一定的效率来换取了一部分空间而已。是否值得，嘿嘿，就得看具体应用了。 

好，闲话说完，下面言归正传。 

话说大家都知道函数调用要压栈。不过这是有几个例外的。 
1。函数是inline的。 
2。语言采用的函数调用方式是continuation, 而不是activation record. 这种模式中语言可以使用堆而不是栈来完成函数调用。 
3。尾调用。也就是说，函数调用出现在调用者函数的尾部，因为是尾部，所以根本没有必要去保存任何局部变量，sp, pc的信息。直接让被调用的函数返回时越过调用者，返回到调用者的调用者去。 
比如： 
f(){g();} g(){h();}


这里，h()函数返回时可以绕过g()函数，f()函数而直接返回到f()函数的调用者。 
注意，尾调用优化不是什么很复杂的优化，实际上几乎所有的现代的高级语言编译器都支持尾调用这个很基本的优化。 
实现层面上，只需要把汇编代码call改成jmp, 并放弃所有局部变量压栈处理，就可以了。所以，很简单。 
我们不考虑continuation这种情况，因为c/c++/java等流行的语言都不是这种模式。 
对于递归，inline也不能使用。因为你不知道你会递归调用多少次。 
于是，就剩下递三条：尾调用。而一个对自己本身的递归尾调用，就叫做尾递归。 
那么，当尾递归时，我们就没有前面分析的递归调用的占用堆栈的缺点，因为每次调用都是尾调用，所以堆栈根本就没有被占用，每次调用都是重新使用调用者的堆栈。 
有些看过ml, haskell这种functional language的程序员可能会奇怪为什么他们不支持循环。 
现在让我们看看他们会怎么实现循环的功能。 


考虑一个简单的例子，求从一加到一百的和。 

用递归， 我们也许可以这样做： 

//普通递归
int sum(int start,int end)
{
	if(start>end)
		return 0;
	else
		return start+sum(start+1,end);
}

 

这个递归函数是可以工作的，唯一的缺点是它会占用很多堆栈空间，也会有很大的压栈出栈的开销。 

于是，我们用尾递归： 

//尾递归
int tail_sum(int seed,int start,int end)
{
	if(start>end)
		return seed;
	else
		return tail_sum(seed+start,start+1,end);
}

 

小小的修改，sum变成了尾递归，没有了对堆栈空间的占用，也没有任何压栈开销。 

注意，这里尾调用的“尾”字，是指运行时需要执行的最后一个动作。不是简单的语法字面上的最后一个语句。 
比如说，c++中，如果我的sum返回的不是int, 而是一个带有有副作用的析构函数的类，那么它就不再是尾递归： 

X sum(X seed, X start, X end){ 
	if(start<end) 
		return seed; 
	else 
		return sum(seed+start, start+1, end); 
}

 

几乎同样的代码，只是不同的类型，但这里，它已经不再是尾递归了！ 
即使这个X类的拷贝构造和析构函数里面通过所有权转移，move semantics减小了拷贝和析构的开销，但，副作用就是副作用，它不再是尾调用了。

分析了一大堆，那么尾递归到底有什么好处呢？呵呵，可读性好，代码强壮，易维护。 

另外，不是所有的递归都可以变成尾递归的。

 

最后附上Fibonacci数列求解的尾递归：

//普通递归
int Fibonacci(int n)
{
	if(n<2)
		return n;
	else
		return Fibonacci(n-2)+Fibonacci(n-1);
}

//尾递归
int tail_Fibonacci(int n,int a1,int a2)
{
	if(n==0)
		return a1;
	else
		return tail_Fibonacci(n-1,a1+a2,a1);
}

 

 

 

过程模拟请见：http://www.cnblogs.com/Anker/archive/2013/03/04/2943498.html