algorithm - 河内塔使用头递归？

Question

我想知道标准的河内塔问题是否可以使用头递归来解决。我有一个模糊的想法，即不可能使用相同编号的圆盘（从 1（最小）到 N（最大）圆盘）和 3 个塔。

标签： algorithmdata-structures

Answer 1

对于您可能的意思的最明智的版本，不。从技术上讲，答案是肯定的。

河内塔问题的重点在于，一个看似简单的问题需要两次递归调用。这立即意味着它不能用尾递归或头递归自然地解决。

然而，该解决方案可以在迭代算法中完全分析和解决。我们可以检查一个位置，计算我们必须在解决方案中的位置，并产生下一个答案。有关此分析的示例，请参见https://www.geeksforgeeks.org/iterative-tower-of-hanoi/ 。

并且可以使用单个迭代循环编写的内容始终可以使用尾递归或头递归从那里重写。通过执行一次迭代然后进行递归调用以在循环中继续，您可以获得尾递归。通过首先进行递归调用以到达当前所需的位置，然后进行当前迭代，您可以获得头部递归。

所以，是的，通过大量的努力，你可以获得头部递归，它伴随着可怕的记忆和性能特征。