Ackermann函数与n重循环

Question

我正在读一本关于计算的书（Minksy 1967），在理解递归函数和用循环定义的函数之间的关系时遇到了一些困难。具体来说，他让我找出两个函数之间的关系：

一个是阿克曼函数（所有代码都是用python写的）：

def a(n,m):
    if n==0:
        return m+1
    if m==0:
        return a(n-1,1)
    return a(n-1,a(n,m-1))

另一个是用n个嵌套循环来计算的函数：

def p(n,m):
    for i_1 in range(m):
        for i_2 in range(m):
           ...
             for i_n in range(m):
                  m+=1

用递归的方式写这个（只有一个循环）是：

def p(n,m):
     if n==0:
         return m+1
     for i in range(m):
         m=p(n-1,m)
     return m

或者完全递归的写法是：

def p(n,m):
    return P(n,m,m)
def P(n,k,m):
    if n==0:
        return m+1
    if k==1:
        return P(n-1,m,m)
    m=P(n,k-1,m)
    return P(n-1,m,m) 

这两个函数之间有没有简单的关系呢？我感觉自己像是在雾里摸索——如果你能给我一些关于如何处理这类问题的见解，我会非常感激。另外，有没有办法在不引入第三个参数的情况下实现完全递归的循环函数？谢谢。

Answer 1

嗯……我觉得这可能对你帮助不大，我也有点困惑，不过这是我的想法。

• Ackerman(0, m) 等于 p(0, m)
• Ackerman(1, m + 1) 等于 p(1, m)

编辑——等一下，我觉得我把函数抄错了。我会再想想这个问题，如果想到什么会更新的！