是否可以将下面的递归函数转换为完全迭代的函数？
def fact(n):
if n <= 1:
return
for i in range(n):
fact(n-1)
doSomethingFunc()
给定额外的空间(如堆栈或队列(似乎很容易做到，但我想知道我们是否可以在O(1(空间复杂性中做到这一点？
注意，我们不能做这样的事情：
def fact(n):
for i in range (factorial(n)):
doSomethingFunc()
因为存储CCD_ 1的结果需要非恒定量的存储器。
一般来说不会。我的意思是，递归函数在堆栈中占用的空间不仅仅是这种编程风格的不便之处。它是计算所需的内存。
所以，当然，对于很多算法来说，这个空间是不必要的，可以省去。对于经典阶乘，例如
def fact(n):
if n<=1:
return 1
else:
return n*fact(n-1)
所有n，n-1，n-2。。。，1论点并不是真正必要的。所以，当然，你可以找到一个摆脱它的实现。但这就是优化(例如，在终端递归的特定情况下。但我非常确信，你添加了"doSomething"，以表明你不想专注于特定情况(。一般来说，你不能假设一个不需要所有这些值的算法存在，无论是递归的还是迭代的。否则，这将意味着所有算法都存在于O(1(空间复杂度版本中。
示例：正整数的基本表示
def baseRepr(num, base):
if num>=base:
s=baseRepr(num//base, base)
else:
s=''
return s+chr(48+num%base)
没有声称它是最佳的，甚至没有写得很好。但是，争论的堆砌是必要的。这是一种隐式存储以相反顺序计算的数字的方式。迭代函数还需要一些内存来存储这些数字，因为您必须首先计算最后一个数字。
好吧，我很确定，对于这个简单的例子，你可以找到一种从左到右计算的方法，例如使用对数计算来提前知道数字的数量或其他什么。但这不是重点。想象一下，除了从右到左计算数字的算法之外，没有其他已知的算法。然后你需要储存它们。要么在使用递归的堆栈中隐式显示，要么在分配的内存中显式显示。因此，堆栈中使用的内存不仅仅是递归带来的不便。这是递归算法存储东西的方式，否则会存储在迭代算法中
注意，我们不能做类似以下的事情：
def fact(n): for i in range (factorial(n)): doSomethingFunc()因为存储CCD_ 2。
是。
我想知道我们是否可以在O(1(空间复杂性中做到这一点？
所以，没有