漫谈递归:递归的效率问题

效率和开销问题是递归最大的缺点
服务器君一共花费了352.509 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

递归在解决某些问题的时候使得我们思考的方式得以简化,代码也更加精炼,容易阅读。那么既然递归有这么多的优点,我们是不是什么问题都要用递归来解决呢?难道递归就没有缺点吗?今天我们就来讨论一下递归的不足之处。谈到递归就不得不面对它的效率问题。

为什么递归是低效的

还是拿斐波那契(Fibonacci)数列来做例子。在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数(不考虑参数小于1或结果溢出等异常情况),我不知你的程序是否会和下列代码类似:

public static ulong Fib(ulong n)
{
    return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
}

这段代码应该算是短小精悍(执行代码只有一行),直观清晰,而且非常符合许多程序员的代码美学,许多人在面试时写出这样的代码可能心里还会暗爽。但是如果用这段代码试试计算Fib(1000)我想就再也爽不起来了,它的运行时间也许会让你抓狂。

看来好看的代码未必中用,如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流,就会发现问题在哪,以计算Fibonacci(5)为例:

从上图可以看出,在计算Fib(5)的过程中,Fib(1)计算了两次、Fib(2)计算了3次,Fib(3)计算了两次,本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显,以至于Fib(1000)已经无法再可接受的时间内算出。

我们当时使用的是简单的用定义来求 fib(n),也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的,可是仔细分析一下我们发现,当调用fib(n-1)的时候,还要调用fib(n-2),也就是说fib(n-2)调用了两次,同样的道理,调用f(n-2)时f(n-3)也调用了两次,而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。

改进的斐波那契递归算法

那么计算斐波那契数列是否有更好的递归算法呢? 当然有。让我们来观察一下斐波那契数列的前几项:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

注意到没有,如果我们去掉前面一项,得到的数列依然满足f(n) = f(n-1) – f(n-2), (n>2),而我们得到的数列是以1,2开头的。很容易发现这个数列的第n-1项就是原数列的第n项。怎么样,知道我们该怎么设计算法了吧?我们可以写这样的一个函数,它接受三个参数,前两个是数列的开头两项,第三个是我们想求的以前两个参数开头的数列的第几项。

int fib_i(int a, int b, int n);

在函数内部我们先检查n的值,如果n为3则我们只需返回a+b即可,这是简单情境。如果n>3,那么我们就调用f(b, a+b, n-1),这样我们就缩小了问题的规模(从求第n项变成求第n-1项)。好了,最终代码如下:

int fib_i(int a, int b , int n)
{
    if(n == 3)
        return a+b;
    else
        return fib_i(b, a+b, n-1);
}

这样得到的算法复杂度是O(n)的。已经是线性的了。它的效率已经可以与迭代算法的效率相比了,但由于还是要反复的进行函数调用,还是不够经济。

递归与迭代的效率比较

我们知道,递归调用实际上是函数自己在调用自己,而函数的调用开销是很大的,系统要为每次函数调用分配存储空间,并将调用点压栈予以记录。而在函数调用结束后,还要释放空间,弹栈恢复断点。所以说,函数调用不仅浪费空间,还浪费时间。

这样,我们发现,同一个问题,如果递归解决方案的复杂度不明显优于其它解决方案的话,那么使用递归是不划算的。因为它的很多时间浪费在对函数调用的处理上。在C++中引入了内联函数的概念,其实就是为了避免简单函数内部语句的执行时间小于函数调用的时间而造成效率降低的情况出现。在这里也是一个道理,如果过多的时间用于了函数调用的处理,那么效率显然高不起来。

举例来说,对于求阶乘的函数来说,其迭代算法的时间复杂度为O(n):

int fact(n)
{
    int i;
    int r = 1;
    for(i = 1; i < = n; i++)
    {
        r *= i;
    }
    return r;
}

而其递归函数的时间复杂度也是O(n):

int fact_r(n)
{
    if(n == 0)
        return 1;
    else
        return n * f(n);
}

但是递归算法要进行n次函数调用,而迭代算法则只需要进行n次迭代而已。其效率上的差异是很显著的。

小结

由以上分析我们可以看到,递归在处理问题时要反复调用函数,这增大了它的空间和时间开销,所以在使用迭代可以很容易解决的问题中,使用递归虽然可以简化思维过程,但效率上并不合算。效率和开销问题是递归最大的缺点。

虽然有这样的缺点,但是递归的力量仍然是巨大而不可忽视的,因为有些问题使用迭代算法是很难甚至无法解决的(比如汉诺塔问题)。这时递归的作用就显示出来了。

递归的效率问题暂时讨论到这里。后面会介绍到递归计算过程与迭代计算过程,讲解得更详细点。

延伸阅读

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

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

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

不打个分吗?

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

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

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

大家都在看

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

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

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

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

《人月神话》 弗雷德里克·布鲁克斯 (作者), 汪颖 (译者)

《人月神话》原文:The Mythical Man-Month: The Essays on Software Engineering, 2nd ed.在软件领域,很少能有像《人月神话》一样具有深远影响力并且畅销不衰的著作。Brooks博士为人们管理复杂项目提供了最具洞察力的见解。既有很多发人深省的观点,又有大量软件工程的实践。本书内容来自Brooks博士在IBM公司System/360家族和OS/360中的项目管理经验。该书英文原版一经面世,即引起业内人士的强烈反响,后又译为德、法、日、俄中等多种语言,全球销量数百万册。确立了其在行业内的经典地位。

更多计算机宝库...