我发现很难理解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?
如有意见将不胜感激。
谢谢
A(3,4)的计算并不像最初从参数的小值中显示的那样简单或简短。阿克曼函数的复杂性(迭代步骤的复杂性)随着参数的增加而迅速增加,计算结果也是如此。
以下是来自Wikipedia的Ackermann函数的定义:
如您所见,在每次迭代中,m的值都会减小,直到达到0为止,这将是最后一步,此时n(+1)的最终值将给出答案。因此,对于答案,您只需要跟踪在递归迭代过程中n的变化。对于Ackermann函数为何增长如此迅速,您可以查看wiki的this小节。
正如Joran Beasley已经提到的,A(3,4)确实是维基百科上写的125。然而,达到这个结果的过程并不短。事实上,正如我发现的,需要通过递归计算315Ackermann函数值来得到A(3,4),所需的迭代次数与此大致成正比。
如果您仍然希望可视化这个结果是如何得到的,那么您可以查看this page,它可以动态地计算每个递归步骤。不过,请注意,A(3,4)在这里完成动画需要花费很长时间,但至少您可以用较小的参数了解这个过程。
下面是一个版本,它打印了一个解释:
对于参数2,2,输出是这样的。(3,4已经有点太多了)
请参见此处的http://goo.gl/jDDEA以可视化
ackerman(2,3)
(可视化3,4太长)相关问题 更多 >
编程相关推荐