尾递归和尾调用

批判< Effective Objective-C 2.0 > 机械工业出版社 译者 爱飞翔

2015-09-25 | 阅读

尾递归

尾递归是指递归操作是函数中最后一个操作的递归情况,举个例子:

int GetSumTo0(int i){
	return i>0? i + GetSumTo0(i-1) : 0;
}

上面是一个普通递归函数,计算从0加到i的和.下面是相应的尾递归写法:

int GetSumTo0(int i,int sum){
	sum += i
	return i>0? GetSumTo0(i-1 ,sum) : 0;
}

使用一个sum参数来保存之前的计算的结果,这样计算到N的时候,之前栈计算的内容,都是可以抛弃不用保存的.这就解决一个递归很重要的问题,即栈溢出.在尾递归中,之前计算的结果都已经积累并以参数的形式交给下一次操作了,之前的函数留存在栈上的数据都可以清空. ** 尾递归使递归在调用堆栈上不会产生堆积 ** .

然后再用最著名的Fibonacci数列来举例,传统的递归是:

int FibonacciRecursively(int n){
	return n < 2 ? n : FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2); 
}

而改成尾递归时,要用尾递归的思路来思考,尾递归是累加,而表示分解.写法为:

int FibonacciTailRecursively(int n, int acc1, int acc2)
{
    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}

调用时传入两个累加器的初始值:

FibonacciTailRecursively(20, 0, 1);

也就是说,把原本的递归的分解问题的思路,变为正常的循环的累加思路.

所以,最后总结

** 尾递归解决了递归的栈溢出问题,但是,将思路转换为循环的思路,导致可读性的下降,而可读性是递归最大的优点 **

尾调用

尾调用为 tail-call,尾递归也是一种尾调用,但是 尾调用并不是尾递归,怒斥翻译爱飞翔,其将尾递归和尾调用优化混为一谈。

尾调用是指 一个函数的最后一个动作是一个函数调用 的情形.称这个调用位置为 尾位置 .如果尾位置调用这个函数自己,那才可以称为 尾递归 .

尾调用的重要性,在于它可以不在调用栈上面添加一个新的堆栈帧–而是更新它 .

当一个函数调用时,电脑必须记住调用函数的位置,即返回位置,才可以在调用结束时带着返回值回到该位置,返回位置一般存在调用栈上,在尾调用的情况下,电脑不需要记住尾调用的位置而是可以从被调用的函数直接带着返回值返回到调用函数的返回位置.尾调用消除即是在不改变当前调用栈的情况下调到新函数的一种优化.

尾调用优化就是以对尾调用这种情况,进行尾调用的消除,以不用添加新的堆栈,只是更新它,来提高效率.只有当某个函数的最后一个操作仅仅是调用其它函数,而不会将其函数返回值另作他用的情况下,进行尾调用优化。