python - 阿克曼函数理解

Question

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

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

我们将不胜感激。

谢谢

Answer 1

A(3,4) 的计算并不像从参数的小值开始看起来那么容易或短。 Ackermann 函数的复杂性(迭代步骤数)随着其参数的增加而迅速增加，计算结果也是如此。

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

如您所见，在每次迭代中，m 的值都会减小，直到它在最后一步达到 0，此时最终值为n (+1) 给你答案。因此，对于答案，您只需要跟踪 n 在递归迭代过程中是如何变化的。为什么阿克曼函数增长如此之快，可以看看this wiki 的子部分。

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

如果您仍然希望直观地了解这个结果是如何得出的，您可以查看 this page ，它为每个递归步骤的计算设置动画。不过请注意，A(3,4) 将永远在这里完成动画，但至少您可以通过较小的参数对过程有所了解。