Uro*_*s K 0 algorithm recursion
如何编写一个countTo(n)从1到n计数的函数并打印每个数字而不使用显式循环(仅递归)？
解决方案必须在空间和时间上渐近最优,即使没有尾调用优化,任意大n.
注意:最佳时间复杂度为O(1),而最佳空间复杂度为O(log n) - 即使在迭代情况下,因为需要打印(任意大的)数字.
问题来自lesswrong.com,相关细节来自那里的讨论(否则问题变得无法回答,因为他们的原始陈述会产生误导性的假设).
如果您希望重写版本仍然是递归的,那就没办法了.任何函数调用都会占用堆栈空间.
有些语言在尾部位置的调用不会消耗堆栈空间.在这些语言中,您可以将函数重写为尾递归,因此它将在O(1)空间中运行.但是,Python不是这些语言之一.