递归程序优化

Question

如何编写一个从1到n计数的函数countTo(n)，并在不使用显式循环(仅递归)的情况下打印每个数字？

该解在空间和时间上必须是渐近最优的，即使没有尾部呼叫优化，给定任意大的n。

注意:最优时间复杂度是O(1)，而最优空间复杂度是O(log )--即使在迭代情况下也是如此，因为需要打印(任意大的)数字。

这个问题来自lesswrong.com，相关的细节来自于讨论(否则问题就无法回答，因为他们最初的陈述是错误的假设)。

Answer 1

如果您希望重写的版本仍然是递归的，则不可能。任何函数调用都会占用堆栈空间。

在有些语言中，处于尾位置的调用不会占用堆栈空间。在这些语言中，您可以重写函数为尾递归函数，因此它将在O(1)空间中运行。然而，Python并不是其中之一。

Answer 2

使用迭代代替递归。

def countTo(n):
    for i in range(1, n + 1):
        print(n)

Answer 3

如果python支持尾递归，则可以这样做：

def foo(n):
    print n
    if n > 1:
        foo(n-1)

与任何现代gcc版本相对应的c程序将在O(1)中运行。不过，我不知道有任何支持尾递归的python解释器--但我不认为语言本身有任何禁止它的限制。