尾递归对时间与空间复杂度的影响
这篇讲的是尾递归在实际应用中那些理论之外的复杂性。文章从一位同学的提问出发：是否所有递归算法都能改写为尾递归？改写后，时间和空间复杂度就一定能得到优化吗？以斐波那契数列为例，表面上似乎验证了这一结论。 作者深入剖析后发现，事情并非如此简单。虽然尾递归确实能通过消除调用栈来优化空间复杂度，但其对时间复杂度的提升是有条件的。文章具体展示了，即使将斐波那契递归改写为尾递归形式（借助累加器参数），若仅仅进行机械转换，得到的依然是一个时间复杂度为 O(2^n) 的低效算法，需要进一步结合动态规划思想才能优化到 O(n)。 文章进而探讨了将一般递归转换为尾递归或迭代的通用方法，分析了转换过程中可能遇到的困难与权衡。结论是，尾递归是一个强大的性能优化工具，但它不是将递归问题转化为高效迭代代码的“万能钥匙”。理解其原理与局限，才能在合适的场景下有效运用它。