将嵌套递归算法（阿克曼函数）转换为迭代算法

Question

我遇到了一个练习题：

我已经为此写出了伪代码，也很容易，只需调用问题陈述中提到的函数即可。但我确实在迭代算法上遇到了困难。然后我遇到了将递归算法转换为迭代算法，这给了我一个想法。

如果我创建一个大小为

(m+1) X (n+1)

的矩阵，并使用 m,n 组合自上而下地求解它，以评估并将结果存储在矩阵中，而不是尝试使用复杂的逻辑和堆栈来模拟调用堆栈，会怎么样？
那行得通吗？或者有更简单的方法吗？

如果有人能给我指出一个不错的资源，教如何将给定的递归算法转换为迭代算法，包括这种嵌套递归，那就太好了。

Answer 1

矩阵的思想也可用于解决其他问题，因为它实际上是动态规划的制表方面。

但是 (𝑚+1)×(𝑛+1) 的矩阵在这里是不够的，因为您提出的阿克曼定义中的第三种情况：它从递归检索的阿克曼数中获取第二个参数，并且该数可以是远大于𝑛的给定值。因此你的矩阵很快就会变得太窄：行数很好，但列数会不足。

您可以调整这个想法，使矩阵在填充时根据需要水平增长。但由于阿克曼值增长得非常快，这很快就会导致内存分配问题。

不过，如果您想针对小阿克曼值测试这个想法，那么这里是该想法在 Python 中的实现：

def ackermann(a, b):
    dp = [[] for _ in range(a+1)]
    
    m = 0
    while len(dp[a]) <= b:  # while we don't have the wanted result yet...
        n = len(dp[m])  # try to get the Ackermann value for the next n for the given m.
        if m == 0:
            n += 1  # first case: this is the Ackermann value
        else:
            n = dp[m][n-1] if n else 1  # second or third case
            if len(dp[m-1]) <= n:  # if we don't have the recursive value yet...
                m -= 1  # go back and solve a simpler case first
                continue
            n = dp[m-1][n]  # we have the needed recursive value
        dp[m].append(n)  # ...store it. 
        if m < a:  # try to get a value for a larger m (if needed)
            m += 1
    return dp[a][b]

矩阵以 𝑚 动态大小的行开始，这些行在开始时为空，但在此过程中会扩展。这个想法是我们尝试计算给定行（𝑚）的下一个水平槽。如果存在我们尚未计算的依赖项，我们会减少 𝑚 并重复尝试，直到解决为止。当它成功时，我们可以再次增加𝑚，...等等

如前所述，这仅适用于小阿克曼数。看这个演示：

for m in range(4):
    for n in range(11):
        ack = ackermann(m, n)
        print(ack, end=" ")
    print()

打印：

1 2 3 4 5 6 7 8 9 10 11 
2 3 4 5 6 7 8 9 10 11 12 
3 5 7 9 11 13 15 17 19 21 23 
5 13 29 61 125 253 509 1021 2045 4093 8189