5

我正在阅读一本关于计算的书(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 个嵌套循环计算的函数:

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) 

这两个功能有什么简单的联系方式吗?我觉得我在迷雾中四处爬行——您能给我的任何关于如何解决这类问题的见解将不胜感激。另外,有没有办法在不引入第三个参数的情况下实现完全递归循环函数?谢谢。

4

1 回答 1

1

嗯......我认为这对你没有多大帮助,我也有点困惑,但这是我的想法。

  • 阿克曼(0, m) == p(0, m)
  • 阿克曼(1, m + 1) == p(1, m)

编辑——等等,我想我抄错了函数。稍后我会再考虑一下,如果我想到什么我会更新!

于 2010-10-24T20:56:10.693 回答