Hello World
Spiga

尾递归对时间与空间复杂度的影响(上)

2011-11-15 22:12 by 老赵, 6126 visits

以前我也在博客上简单谈过“尾递归”及其优化方式方面的话题。前几天有同学在写邮件向我提问,说是否所有的递归算法都能改写为尾递归,改写成尾递归之后,是否在时间和空间复杂度方面都能有所提高?他以斐波那契数列为例,似乎的确是这样的情况。我当时的回答有些简单,后来细想之后似乎感觉有点问题,而在仔细操作之后发现事情并没有理论上那么简单,因此还是计划写篇文章来讨论下这方面的问题。

斐波那契数列

大家对于斐波那契数列(Fibonacci)的认识一定十分统一,唯一的区别可能仅在于n是从0开始还是从1开始算起。这里我们使用维基百科上的标准递归定义

其边界情况为:

使用这个定义可以直接写出程序,这里我们用F#来表达:

let rec fib n =
    if n < 2 then n
    else fib (n - 1) + fib (n - 2)

这个算法最容易理解,但其时间复杂度确是:

这种指数级的时间复杂度在实际应用中是十分可怕的(虽然这个数字是美妙的黄金分割)。因此,我们如果真要“计算”斐波那契数列第n项的值(即不使用“通项公式”),则往往会使用迭代的方式进行,写作尾递归则是:

let fibTail n = 
    // 第i项的值v1,以及即将累加上去的值v2
    let rec fibTail' i v1 v2 =
        if i >= n then v1
        else fibTail' (i + 1) (v1 + v2) v1
    fibTail' 0 0 1

从代码上也可以轻易地判断出,这个算法的时间复杂度是O(n),实际上它也会被F#或是Scala等支持尾递归的编译器优化为循环操作。这里我们使用命令式编程语言C#来表达编译后的结果:

static int FibTail(int n, int i, int v1, int v2)
{
    while (i < n)
    {
        int temp = v1 + v2;
        v2 = v1;
        v1 = temp;
        i++;
    }

    return v1;
}

时间复杂度从O(1.618n)降低到O(n),可谓是质的飞跃。

尾调用对空间复杂度的影响

那么,在空间复杂度方面,尾递归带来什么优化吗?我们首先还是来分析标准的递归算法:

假设,我们知道,在一个(无副作用的)方法执行完毕之后,除了返回值以外的空间会完全释放出来,因此在fib(n - 2)执行结束之后,它的空间占用是常数级的。且fib(n - 1)的空间占用一定大于fib(n - 2),假设其fib(n)的空间占用为S(n),可得:

于是fib的空间复杂度是显而易见的O(n)。这个空间复杂度其实并不大,例如经典的归并排序算法的空间复杂度也同样是O(n)。但不幸的是,这里的递归操作占用的完全是栈空间,而栈空间的大小是极其有限的(例如一个Windows应用程序默认情况下只有1M,ASP.NET甚至只有250K)。因此,只需一个稍大一点的数字会产生栈溢出。经试验,在我的机器上只需51K便能出现StackOverflowException:

// 50K不会出现StackOverflowException
51 * 1024 |> fib |> printfn "%d"

那么尾递归算法的空间复杂度呢?我们刚才提到,编译器会将尾递归优化成循环,那在实际运行时这个算法的空间复杂度自然是常数级,即O(1)。但这是我们实际观察到的编译器优化后的结果,从理论上说,我们并无法保证这里的尾递归会被优化成循环。因此我们不妨也从“字面”上来理解代码,看看理论上这样的尾递归调用会形成怎样的空间占用。

对于尾递归来说,理论上我们只能期待它形成“尾调用”。也就是说,针对某个方法的调用(无论是否是递归操作)是父方法的最后一个操作。在这个情况下,我们无需保留父方法当前的栈空间,因此可以将其完全释放。于是,无论调用多少次,只要每次都将栈空间释放(或重用),其空间占用也始终是个常数,即O(1)。

因此,无论从理论上(从字面上分析)还是实际上(观察编译结果)来说,似乎将斐波那契数列修改为尾递归,能显著地降低时间及空间复杂度,这也是那位同学提出“尾递归能改进时间和空间复杂度”的依据。那么我们重新回顾一下文章开头所提出的两个问题:

  • 每个递归算法都能改写为尾递归吗?
  • 改写为尾递归都能改进时间及空间复杂度吗?

下次我们继续讨论这两个问题。

相关文章

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

39 条回复

  1. mathgl
    42.2.25.*
    链接

    mathgl 2011-11-16 01:03:45

    篇幅和上一篇比较..貌似不需要分为两部分呀...

  2. 四有青年
    114.80.125.*
    链接

    四有青年 2011-11-16 09:31:06

    这个貌似属于SICP里讨论的范畴,期待下文

  3. 老赵
    admin
    链接

    老赵 2011-11-16 09:42:26

    @mathgl

    是的,我现在挺懒的,感觉差不多可以算作一篇了就不写长了……

  4. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-16 12:08:56

    老赵,我问下我用jscex在ie9以下的浏览器失效了,但是在火狐谷歌里都没问题,不知道是咋回事?都有哪几种可能呀?我引入json2.js了,还需要什么呢?

  5. kusk
    118.26.185.*
    链接

    kusk 2011-11-16 13:20:01

    递归/尾递归/消除递归,只是实现形式。褪去这个外壳,时/空复杂度的本质其实还是算法,只不过递归可能恰好拟合了某些算法的记法而已。所以“将Fib递归程序改为尾递归”,本质上其实是“将Fib的逆推算法改为迭代算法”。至于说这些算法是用递归来写,还是用非递归来写(包括最初的指数级算法,当然也可以用非递归形式实现)。所以原问题探讨的递归或是不递归,其实不是究竟。关键在于算法本身(如本例中的Fib)是否有进一步化简的潜力。

  6. Zealot
    114.113.197.*
    链接

    Zealot 2011-11-16 13:33:52

    你这篇文章里有两个重大错误:

    1. 你把递归的fib转换成尾递归的fib时偷换了概念

    你不仅仅使用了尾递归技巧, 而且还使用了DP(Dynamic Programming),原始的Fib(n)内部是不知道Fib(n-1)与Fib(n-2), 但是转换后的fibTail(n)知道fibTail(n-1)与fibTail(n-2), 这是DP不是尾递归变换

    你结论中的“将斐波那契数列修改为尾递归,都能显著地降低时间及空间复杂度”,完全是错误的。实际上应该是“使用DP计算斐波那契数列,能显著地降低时间及空间复杂度"

    2. 尾递归不会改变程序的空间复杂度和时间复杂度

    先理解一下CPS变换(这里使用JavaScript作为实例代码)

    function nonTail(args) {
       var which_use_stack = { ... };
       return nonTail(step(args)) + which_use_stack;
    }
    

    对这个函数做CPS变换:

    function tail(k, args) {
        var which_use_stack = { ... };
        return k(tail(function (value) {
            return value + which_use_stack;
        }, step(args)))
    }
    

    这里很明显可以看出, whichusestack本来使用的是堆栈空间, 现在使用的空间转移到闭包中了(tail的第一个参数, continuation闭包). 得到这个结论, 就说明你了解了尾递归, 尾递归的作用是把所需的栈空间转移到闭包里面, 仅仅是为了节约栈空间!

    对于时间复杂度, 你不修改算法本身, 怎么可能有变化?!

    尾递归变化仅仅是一个等价变化, 猫变咪, 咪变猫. 你这整篇文章都是在讲DP, 不是尾递归.

  7. 老赵
    admin
    链接

    老赵 2011-11-16 14:19:38

    @Zealot: 你结论中的“将斐波那契数列修改为尾递归,都能显著地降低时间及空间复杂度”,是完全是错误的。实际上应该是“使用DP计算斐波那契数列,能显著地降低时间及空间复杂度”。

    急啥,这又不是我的观点,是那位提问的同学的观点。我这不是还没有回答这两个问题么,这不是还有下一篇文章么。其实如果你看看“相关文章”里的两篇文章也该知道我会说什么了吧,嘿嘿……

  8. 老赵
    admin
    链接

    老赵 2011-11-16 14:21:03

    @lovejjhao

    什么错误?我那些例子都可以在IE 9下面跑的,比较下有什么不同吧。

  9. Zealot
    114.113.197.*
    链接

    Zealot 2011-11-16 14:25:42

    老赵你把时区改一下吧, 大家都成夜猫子了.

    发现 @kusk 已经在我发评论之前说出问题所在了, 赞啊

  10. 老赵
    admin
    链接

    老赵 2011-11-16 14:30:57

    @Zealot

    我什么时候不懒了会改很多东西的……

  11. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-16 14:47:01

    恩,我这也是ie9可以跑,但是ie8,ie7就不行了......我是调用异步函数的start(),报找不到对象,异步方法为undefined

  12. 老赵
    admin
    链接

    老赵 2011-11-16 14:50:50

    @lovejjhao

    我的示例也不能跑?不要告诉我你跑了用Canvas的那些。

  13. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-16 14:59:34

    没试呢还。。。。我试试去,是自己写的例子。没跑那些~知道浏览器不支持~呵呵,我查查是不是自己哪些的不对

  14. Zealot
    114.113.197.*
    链接

    Zealot 2011-11-16 15:12:05

    那么你这篇只有(上)的误导性确实太强了, 这里只看(上)没有(下)不是要栽沟里面了么?

    还是上下一起贴出来吧。

  15. 老赵
    admin
    链接

    老赵 2011-11-16 15:16:26

    @Zealot

    我觉得挺好的,正好害害那些看文章不看完,或者自己不思考的人,嘿嘿。

  16. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-16 16:42:19

    原来是我把

    <script language="javascript" type="text/javascript" src="scripts/json2.js"></script>
    <script language="javascript">
        Jscex.config.codeGenerator = function(code) { return "false || " + code; }
    </script>
    

    加到了最开始......

  17. 老赵
    admin
    链接

    老赵 2011-11-16 16:51:14

    @lovejjhao

    其实如果是这样的话,看看Error Console里有哪些消息就能立即知道问题了……

  18. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-16 17:00:35

    怎么查看Error Console呀?

  19. 老赵
    admin
    链接

    老赵 2011-11-16 17:32:59

    @lovejjhao

    每个浏览器都有Developer Tools,难道你都是靠猜的么……

  20. mcpssx
    59.175.192.*
    链接

    mcpssx 2011-11-17 08:22:53

    每个递归算法都能改写为尾递归吗?

    我记得《数据结构》说过所有递归都可以转换为迭代,而尾递归函数是一个迭代循环体参数化为函数,所以我认为理论上递归算法都能改写为尾递归。

    改写为尾递归都能改进时间及空间复杂度吗?

    尾递归比递归占用空间小,是因为递归需要保存每步的栈空间,而尾递归只需要保存他依赖的一步的结果,所以除非尾递归需要之前所有步的结果,尾递归占用的空间应该比递归小,换一个思路看,迭代要保存的中间数据一般都比递归小,而尾递归应该与迭代时空复杂度相同。

    最后,我认为尾递归优化是一个发展过程的暂时结果,编译器不但可以支持尾递归优化,也应该支持一个pure函数的递归优化。

  21. lovejjhao
    123.180.118.*
    链接

    lovejjhao 2011-11-17 09:40:07

    楼上的,你又来了......

  22. 老赵你这为什么不能用QQ登陆啊
    210.75.15.*
    链接

    老赵你这为什么不能用QQ登陆啊 2011-11-17 11:24:13

    老赵你这为什么不能用QQ登陆啊,那些啥账号我都木有啊。呵呵 qq不是开放了么 用QQ登陆多好哇

  23. 靖难
    202.120.50.*
    链接

    靖难 2011-11-18 12:00:43

    有很多算法改写成尾递归其实和迭代就是一回事,只是把之前依赖的结果做为参数传入了。在函数式编程语言中,不提供像for,while这样的循环机制,一般就直接用尾递归来实现了.

    尾递归只是同一算法的迭代的另一种等价描述方式,我认为不能减少时间复杂度。空间复杂度这个问题我也没搞得完全懂,感觉似乎减少了栈空间,但是每次需要传递的参数也增加了。

  24. 老赵
    admin
    链接

    老赵 2011-11-18 15:26:46

    @靖难

    菲波纳契数列的递归算法又没有用到for和while,还有递归的空间复杂度是什么你没搞清楚……

  25. 靖难
    202.120.50.*
    链接

    靖难 2011-11-18 16:03:50

    @老赵

    难道递归的空间复杂度不是用于保存返回地址的堆栈的深度么?

    我又没有说菲波纳契的递归算法用到for while了,我只是说尾递归可以替代for while来实现迭代的功能,二者是等价的.菲波纳契的尾递归算法也等价于他的迭代算法,我只是表达一个这样的观点。

    你可以解释解释递归的空间复杂度么,大牛~

  26. 靖难
    202.120.50.*
    链接

    靖难 2011-11-18 16:10:36

    上下文之间是不是注明以下哪些观点是你自己的,哪些是你引用的别人的观点比较好,大牛不管犯什么错误总能给自己找到台阶下~

  27. 老赵
    admin
    链接

    老赵 2011-11-18 22:43:07

    @靖难: 难道递归的空间复杂度不是用于保存返回地址的堆栈的深度么?

    是啊,就是指保存返回地址堆栈的深度,那么你说关参数大小什么事情?只要不积累堆栈,就算每次“压栈”参数尺寸增大100倍,那时间复杂度就还是降低了。你之前说“空间复杂度这个问题我也没搞得完全懂,感觉似乎减少了栈空间,但是每次需要传递的参数也增加了”又是指什么?,在我看来就是没搞清楚“复杂度”和“大小”么。

    还有请看最后一段文字,“似乎”和“那位同学”什么的写在那里清清楚楚,不要把自己没看清文章内容说成是我在找台阶下。更何况我都写明下一篇文章再讨论这两个问题,这么简单的问题有什么值得犯错的。讨论技术就讨论技术,好的不学就学会诛心了么。

  28. ofey
    119.253.36.*
    链接

    ofey 2011-11-21 15:41:08

    请教一下这个博客是用什么搭建的?

  29. 老赵
    admin
    链接

    老赵 2011-11-21 20:48:47

    @ofey

    自己写的。

  30. ofey
    119.253.36.*
    链接

    ofey 2011-11-22 09:17:07

    界面看着挺舒服的。

    前后端分别用的什么技术?

  31. 老赵
    admin
    链接

    老赵 2011-11-22 14:18:47

    @ofey

    编程技术。

  32. ofey
    119.253.36.*
    链接

    ofey 2011-11-22 16:05:49

    我晕。。

    .net + sqlserver?

  33. 老赵
    admin
    链接

    老赵 2011-11-22 19:24:10

    @ofey

    没用SQL Server,用了MongoDB。

  34. CoderNet
    183.250.26.*
    链接

    CoderNet 2011-11-23 16:01:26

    老赵...去IBM了没、?

  35. 老赵
    admin
    链接

    老赵 2011-11-23 19:10:57

    @CoderNet

    都四个月了。

  36. 麦子
    58.41.19.*
    链接

    麦子 2011-11-27 10:05:39

    mongodb的时间很让人蛋疼,还是用数字存好些。

  37. c
    222.205.108.*
    链接

    c 2012-09-03 23:20:09

    尾递归对时间与空间复杂度的影响(下)为什么打不开呢,这样太坑爹了

  38. 链接

    杰 余 2013-01-07 22:20:51

    个人观点:递归和尾递归运行次数不变,递归的深度还是那样深。 空间占用:尾递归比递归小。尾递归只保存最后一次的变量,期间的变量都删除了,所以占用空间小。。

  39. friskfly
    112.86.213.*
    链接

    friskfly 2013-06-12 16:40:32

    搜了一下,好像没有 (下)篇 啊

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我