两个递归称为无完成(河内塔)

Question

我在编程这个功能哈斯克尔河内问题的塔.该功能提供了从源棒到目标棒的步数,只有一个替代棒.

numStepsHanoi :: Integer -> Integer
numStepsHanoi 0 = 0
numStepsHanoi n = numStepsHanoi (n-1) + numStepsHanoi (n-1) + 1

此功能工作正常......直到n,光盘数量太高.GHCi没有完成.我知道这个问题的复杂性,我知道它不能运行得更快.

例如,如果我调用它n = 64,我可以等待20分钟并且没有输出(它没有完成).即使n = 20,大约需要2秒钟.

通过另一个实现(下面),时间大大减少了.

numStepsHanoi :: Integer -> Integer
numStepsHanoi 0 = 0
numStepsHanoi n = 2 * numStepsHanoi (n-1) - 1

现在,有了n = 64,我立刻得到了结果.显然这只有一个递归调用,但是它有这么大的影响吗？

这可能是GHCi优化的问题吗？

Answer 1

我怀疑这实际上是函数的复杂性.您的第一个版本为每次调用进行2次递归调用,复杂度为O(2 ^ n).对于n = 64,您正在进行2 ^ 65 - 1次总呼叫.这大约是37*10 ^ 18次调用,因此您不会在当前的计算能力下看到这一生命中的结果.每微秒一次呼叫,这仍然超过1000万年.

第二个例程每次迭代只进行一次调用; 这是O(n).

要查看效果,请尝试在n = 19,20,21,22处计时您的第一个功能.这应足以显示每个添加的光盘的2倍时差.