文章/答案/技术大牛

发布

社区首页 >问答首页 >Ackermann函数理解

问Ackermann函数理解
EN

Stack Overflow用户

提问于 2012-10-02 01:30:36

回答 4查看 23.4K关注 0票数 10

我发现很难理解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？

评论将不胜感激。

谢谢

python

function

recursion

回答 4

Stack Overflow用户

回答已采纳

发布于 2012-10-02 02:13:09

从参数的较小值来看，A(3,4)的计算并不像乍看起来那么简单或简短。随着参数的增加，Ackermann函数的复杂度(迭代步数)增长非常快，计算结果也是如此。

下面是来自Wikipedia的Ackermann函数的定义

正如您所看到的，在每次迭代中，m的值都会减少，直到它到达，这将是最后一步，在这一步，n (+1)的最终值将为您提供答案。因此，对于答案，您只需跟踪n在递归迭代过程中如何变化。要了解为什么Ackermann函数增长如此之快，您可以查看维基的小节。

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

如果您仍然希望可视化此结果是如何得出的，您可以查看，它为每个递归步骤的计算提供了动画效果。不过，需要注意的是，A(3,4)将永远不会完成这里的动画，但至少您可以通过较小的参数对该过程有一些了解。

票数 15

Stack Overflow用户

发布于 2012-10-02 02:30:25

下面是一个打印解释的版本：

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

票数 9

Stack Overflow用户

发布于 2012-10-02 01:36:35

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)

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/12678099

复制

相似问题

问Ackermann函数理解
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Ackermann函数理解EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Ackermann函数理解
EN