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