如何编写一个从1到n计数的函数countTo(n),并在不使用显式循环(仅递归)的情况下打印每个数字?
在给定任意大n的情况下,即使没有尾部调用优化,解在空间和时间上也必须是渐近最优的。
注意:最佳的时间复杂度为O(1),而最佳的空间复杂度为O(log n)-即使在迭代的情况下,因为(任意大)的数量需要打印。
这个问题来自lesswrong.com,相关的细节来自那里的讨论(否则这个问题就无法回答,因为他们最初的陈述会产生误导性的假设)。

最佳答案

如果您希望重写的版本仍然是递归的,那就没有办法了。任何函数调用都将占用堆栈空间。
有些语言中处于尾部位置的调用不会占用堆栈空间。在这种语言中,你可以重写你的函数,使之成为尾部递归的,这样它就可以在O(1)空间中运行然而,Python不是这些语言之一。

10-08 04:18