10

我发现很难理解阿克曼函数是如何工作的。我认为我对递归的理解有缺陷？

这是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？

评论将不胜感激。

谢谢

4

4 回答 4

16

A(3,4)的计算并不像最初从参数的小值中看到的那样简单或短。Ackermann 函数的复杂性（迭代步数）随其参数增长得非常快，计算结果也是如此。

这是来自Wikipedia的 Ackermann 函数的定义：

在此处输入图像描述

正如你所看到的，在每次迭代中，m的值都会减小，直到它在最后一步达到0 ，此时n (+1) 的最终值会给你答案。因此，对于答案，您只需要跟踪递归迭代中n的变化情况。关于 Ackermann 函数增长如此迅速的原因，您可以查看 wiki 的这个小节。

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

如果您仍希望可视化如何得出此结果，您可以查看此页面，该页面为每个递归步骤的计算提供动画。但请注意，A(3,4)将永远完成此处的动画，但至少您可能会通过较小的参数对这个过程有所了解。

于 2012-10-01T18:13:08.553 回答
9

这是一个打印解释的版本：

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
于 2012-10-01T18:30:24.617 回答
3 
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 太长了）

于 2012-10-01T17:36:34.830 回答
0 
def ackermann(m,n):
    """computes the value of the Ackermann function for the input integers m and n.
       the Ackermann function being:
       A(m,n)=n+1               if m=0
             =A(m-1,1)          if m>0 and n=1
             =A(m-1,A(m,n-1)    if m>0 and n>0"""
    if m==0:
        print (n+1)
        return n+1
    elif m>0 and n==0:
        print ("ackermann(",m-1,",",1,")")                                          #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
        return ackermann(m-1,1)
    elif m>0 and n>0:
        print ("Ackermann(",m-1,",","Ackermann(",m,",",n-1,")",")")                  #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
        return ackermann(m-1,ackermann(m,n-1))

只需对您的代码进行简单修改，以便程序打印每个步骤而不仅仅是结果。代码应该看起来有点像本页末尾的内容。运行它，（可能需要几秒钟），然后您就会了解如何计算 Ackermann 函数。

于 2016-11-27T17:58:29.863 回答