尾递归对时间与空间复杂度的影响
以前我也在博客上简单谈过“尾递归”及其优化方式方面的话题。前几天有同学在写邮件向我提问,说是否所有的递归算法都能改写为尾递归,改写成尾递归之后,是否在时间和空间复杂度方面都能有所提高?他以斐波那契数列为例,似乎的确是这样的情况。我当时的回答有些简单,后来细想之后似乎感觉有点问题,而在仔细操作之后发现事情并没有理论上那么简单,因此还是计划写篇文章来讨论下这方面的问题。
斐波那契数列
大家对于斐波那契数列(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)。
因此,无论从理论上(从字面上分析)还是实际上(观察编译结果)来说,似乎将斐波那契数列修改为尾递归,能显著地降低时间及空间复杂度,这也是那位同学提出“尾递归能改进时间和空间复杂度”的依据。那么我们重新回顾一下文章开头所提出的两个问题:
下次我们继续讨论这两个问题。
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:老赵 来源: 老赵点滴
- 标签: 尾递归
- 发布时间:2012-08-28 23:17:39
- [71] Twitter/微博客的学习摘要
- [65] find命令的一点注意事项
- [65] IOS安全–浅谈关于IOS加固的几种方法
- [62] 如何拿下简短的域名
- [62] android 开发入门
- [62] Go Reflect 性能
- [61] Oracle MTS模式下 进程地址与会话信
- [60] 流程管理与用户研究
- [57] 【社会化设计】自我(self)部分――欢迎区
- [57] 图书馆的世界纪录