algorithm - 递归程序优化

Question

如何编写函数 countTo(n) 从 1 计数到 n 并打印每个数字而不使用显式循环(仅递归)？

给定任意大的 n，即使没有尾调用优化，解决方案也必须在空间和时间上渐近最优。

注意:最佳时间复杂度为 O(1) 而最佳空间复杂度为 O(log n) – 即使在迭代情况，因为需要打印(任意大的)数字。

问题来自lesswrong.com ，相关细节取自那里的讨论(否则问题变得无法回答，因为他们的原始陈述做出了误导性的假设)。

Answer 1

如果想让重写后的版本仍然是递归的，那是没有办法的。任何函数调用都会占用堆栈空间。

在某些语言中，位于尾部位置的调用不会占用堆栈空间。在这些语言中，您可以将函数重写为尾递归，这样它就可以在 O(1) 空间内运行。然而，Python 不是其中一种语言。