尾递归优化的效果到底有多明显?

尤里2号   ·  10月前   ·   后端语言

什么是递归

程序调用自身的编程技巧称为递归(recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

简单来说,递归的核心思想是:我不知道这个问题的答案f(n)是什么,但是我知道答案可以由规模更小的、相似的问题的答案f(n-1)来求出,而碰巧f(n-1),f(n-2)...等问题都有这个特性,且问题规模小到一定程度我们可以直接取得结果,那么f(n)就是可解的。

以斐波那契数列为例,事实上这也是学习递归的经典问题之一。
斐波那契数列:0,1,1,2,3,5,8,13,21,34...
我们发现这个数列从第三项开始都有一个规律:当前项等于前两项之和,所以可以用数学语言去描述它
fib(n)=0 (n=0)
fib(n)=1 (1=<n<2)
fib(n)=fib(n-1)+fib(n-2) (n>2)
其实这种数学语言已经很接近伪代码,稍作加工就可以用程序语言描述。

什么是尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

通俗来说,尾递归可以理解为:这个递归函数的递归调用,总是在末尾,而且调用形式是简单粗暴的返回(如return fib(n-1))。

为什么尾递归能优化执行效率

我们知道递归是需要大量函数调用和回溯的,这都需要比较大的系统开销。
以计算fib(5)为例,经典计算过程如下:

  1. fib(5)=fib(4)+fib(3)
  2. fib(5)=fib(3)+fib(2)+fib(3)
  3. fib(5)=fib(2)+fib(1)+fib(2)+fib(3)
    ...

可以预见到,程序在尝试计算fib(4)的时候,一直惦记着一件事情:后面还有一个fib(3)没算呢!所以第一行的现场环境一直被保留了下来,同理其他递归调用的上层环境也是层层保留,等着底层的回溯。


下面我们尝试换一种递归描述(使用尾递归优化)
设fib(n,current,next)
那么fib(n,current,next)=fib(n-1,next,current+next)
其中n代表还需递归次数,current代表当前项值,next代表下一项值

这里可能有点难懂,要好好想想为什么这个等式成立

所以计算fib(n)的过程如下:

  1. fib(n)=fib(n,0,1) //初始化,当前值0(数列的第0项),下一项为1
  2. fib(n)=fib(n-1,1,1)
  3. fib(n)=fib(n-2,1,2)
  4. fib(n)=fib(n-3,2,3)
  5. fib(n)=fib(n-4,3,5)
  6. fib(n)=fib(n-5,5,8)
  7. fib(n)=fib(n-6,8,13)
  8. fib(n)=fib(n-7,13,21)
    ...
    当n<=0,输出fib(n)=current

可以看出,这个计算过程,比起普通的递归过程,要整齐的多。对于编译器来说,由于每次递归都在函数的最后,它可以不用等待下层回溯,直接把它看做是在同一个函数体内继续执行。这样本来开销很大的层层调用就变成了迭代。

眼见为实

没有什么比实际测试更有说服力了,下面我们将对比经典算法和尾递归优化后的斐波那契数列算法执行效率。

以常见的JavaScript为程序语言
fib1:普通递归
fib2:尾递归优化后的递归
fib3:无递归,迭代(理论上是最快的)

//普通递归
function fib1(n) {
    return n<=2?1:fib1(n-1)+fib1(n-2);
}

//尾递归优化,打包初始值n,0,1
function fib2(n) {
    return fibRel2(n,0,1)
}
function fibRel2(n,current,next) {
    if(n===0) return current;
    return fibRel2(n-1,next,current+next)
}

//迭代
function fib3(n) {
    var current=0,next=1,swap;
    for(var i=0;i<=n;i++){
        swap=current;
        current=next;
        next=next+swap;
    }
    return current;
}

经测试,计算fib(30)的耗时(单位:ms)
fib1: 11.519
fib2: 0.108
fib3: 0.028

结论:经过尾递归优化的算法比普通算法要快100倍左右,但是尾递归优化的算法比起迭代算法还是差了5倍左右。
读者也可以按F12复制代码用浏览器当场测试一下。

迭代算法:你们这群垃圾(笑)

1.这里并不是说因为执行效率就否定递归算法。事实上一些算法根本很难用迭代来实现,也不一定可以方便地去做尾递归优化,所以具体该用什么算法还是要看实际情况的。
2.关于递归及尾递归的定义摘自百度百科


3 条回复   |  直到 10月前 | 469 次浏览

lovefc 10月前 支持  0 | 反对  0

打破零回复

ccdalao 10月前 支持  0 | 反对  0

打破一回复惨案

登录后才可发表内容