阿克曼函数与n个嵌套循环

Question

我正在读一本关于计算的书（Minksy 1967），我很难把递归函数和循环定义的函数联系起来。他特别要求找出两个函数之间的关系：

Ackermann函数（所有代码都是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个嵌套循环进行计算的函数：

^{pr2}$

写这个的递归方法（使用一个循环）是：

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

嗯。。。我不认为这对你有多大帮助，我也有点困惑，但这是我的想法。在

• 阿克曼（0，m）==p（0，m）
• 阿克曼（1，m+1）==p（1，m）

等等，我想我把函数复制错了。稍后我会再考虑这个问题，如果我想到了什么，我会更新的！在