能否将指定递归函数转换为O(1)空间复杂度的纯迭代函数？

首先明确原递归函数的执行逻辑：调用fact(n)时，会循环n次，每一轮先递归执行fact(n-1)（完成该子调用中所有doSomethingFunc()的执行），然后自身执行一次doSomethingFunc()。

O(1)空间实现的结论 #

无法在严格O(1)额外空间复杂度下实现等价的迭代版本，核心原因如下：

• 原递归的执行是嵌套的深度优先过程，每进入一层fact(k)，需要跟踪当前循环的进度（已完成多少次迭代）。当从子递归fact(k-1)返回后，必须回到fact(k)的循环继续处理剩余迭代，这需要保存上一层的循环状态信息。
• 若不使用栈、队列等O(n)空间的数据结构，无法存储这些嵌套层次的状态。如果尝试用固定数量的变量编码所有状态，变量的取值范围会随n指数级增长，存储该变量所需的内存会随n增大而增加，不符合“恒定额外内存”的O(1)空间要求。

O(n)空间的迭代实现（参考） #

如果允许使用O(n)空间，用栈模拟递归上下文的实现很直接：

def fact_iter(n):
    # 栈元素：(当前处理的k值, 当前循环次数, 是否从子调用返回)
    stack = [(n, 0, False)]
    while stack:
        k, i, returned = stack.pop()
        if k <= 1:
            continue
        if not returned:
            # 保存当前循环的下一次迭代状态，先进入子递归
            stack.append((k, i, True))
            stack.append((k-1, 0, False))
        else:
            # 从子递归返回，执行一次doSomething
            doSomethingFunc()
            # 还有剩余循环的话，继续处理
            if i + 1 < k:
                stack.append((k, i+1, False))

内容的提问来源于stack exchange，提问作者Mathphile