阿克曼函数理解

2024-03-29 05:35:59 发布

您现在位置:Python中文网/ 问答频道 /正文

我发现很难理解Ackermann函数是如何工作的。我认为我对递归的理解有缺陷吗?

下面是Python中的代码:

  def naive_ackermann(m, n):
    global calls
    calls += 1
    if m == 0:
        return n + 1
    elif n == 0:
        return naive_ackermann(m - 1, 1)
    else:
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1))

如果我执行naive_ackermann(3,4)的函数调用,如何以及为什么最终得到125?

如有意见将不胜感激。

谢谢


Tags: 函数代码returnifdefglobalelse意见
3条回答

A(3,4)的计算并不像最初从参数的小值中显示的那样简单或简短。阿克曼函数的复杂性(迭代步骤的复杂性)随着参数的增加而迅速增加,计算结果也是如此。

以下是来自Wikipedia的Ackermann函数的定义:

enter image description here

如您所见,在每次迭代中,m的值都会减小,直到达到0为止,这将是最后一步,此时n(+1)的最终值将给出答案。因此,对于答案,您只需要跟踪在递归迭代过程中n的变化。对于Ackermann函数为何增长如此迅速,您可以查看wiki的this小节。

正如Joran Beasley已经提到的,A(3,4)确实是维基百科上写的125。然而,达到这个结果的过程并不短。事实上,正如我发现的,需要通过递归计算315Ackermann函数值来得到A(3,4),所需的迭代次数与此大致成正比。

如果您仍然希望可视化这个结果是如何得到的,那么您可以查看this page,它可以动态地计算每个递归步骤。不过,请注意,A(3,4)在这里完成动画需要花费很长时间,但至少您可以用较小的参数了解这个过程。

下面是一个版本,它打印了一个解释:

def A(m, n, s="%s"):
    print s % ("A(%d,%d)" % (m, n))
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1, s)
    n2 = A(m, n - 1, s % ("A(%d,%%s)" % (m - 1)))
    return A(m - 1, n2, s)

print A(2,2)

对于参数2,2,输出是这样的。(3,4已经有点太多了)

A(2,2)
A(1,A(2,1))
A(1,A(1,A(2,0)))
A(1,A(1,A(1,1)))
A(1,A(1,A(0,A(1,0))))
A(1,A(1,A(0,A(0,1))))
A(1,A(1,A(0,2)))
A(1,A(1,3))
A(1,A(0,A(1,2)))
A(1,A(0,A(0,A(1,1))))
A(1,A(0,A(0,A(0,A(1,0)))))
A(1,A(0,A(0,A(0,A(0,1)))))
A(1,A(0,A(0,A(0,2))))
A(1,A(0,A(0,3)))
A(1,A(0,4))
A(1,5)
A(0,A(1,4))
A(0,A(0,A(1,3)))
A(0,A(0,A(0,A(1,2))))
A(0,A(0,A(0,A(0,A(1,1)))))
A(0,A(0,A(0,A(0,A(0,A(1,0))))))
A(0,A(0,A(0,A(0,A(0,A(0,1))))))
A(0,A(0,A(0,A(0,A(0,2)))))
A(0,A(0,A(0,A(0,3))))
A(0,A(0,A(0,4)))
A(0,A(0,5))
A(0,6)
7
ackerman(3,4) 

=ackerman(2,ackerman(3,3)) = ackerman(2,61)    #ackerman(3,3) = 61 ...
=ackerman(1,ackerman(2,60)) = ackerman (1,123)  #ackerman(2,60) = 123...
=ackerman(0,ackerman(1,122)) = ackerman (0,124)  #ackerman(1,122) = 124...
= 124+1 = 125

请参见此处的http://goo.gl/jDDEA以可视化ackerman(2,3)(可视化3,4太长)

相关问题 更多 >