algorithm - 汉诺塔使用头部递归？

Question

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

Answer 1

对于您的意思的最合理版本，不。从技术上讲，答案是肯定的。

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

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

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

所以是的，通过大量的努力，您可以获得 head 递归及其伴随的可怕的内存和性能特征。