关于汉诺塔递归算法时间复杂度的一个问题
A question regarding the tower of hanoi recursive algorithm time complexity
我今天正在进行编码练习。考试结束后，查看成绩，遇到一道题目，题目表述如下：
给定汉诺塔问题中的 4 个圆盘，递归算法最多调用同一个函数 ___ 次。
A. 10
B. 16
C.22
D.31
我唯一知道的是我选了B.16，我错了。
上网查了下发现应该是2n - 1次，也就是15次。
但是，它不在选项中。
哪个选项是正确的？
任何建议将不胜感激。
谢谢。
4 盘拼图需要 15 步。不过，递归调用的次数取决于它的实现方式。
如果您的递归基本情况是 1 个磁盘 => 1 次移动，那么它是 15。如果您的递归基本情况是 0 个磁盘 => 0 次移动，那么它是 31。
我今天正在进行编码练习。考试结束后，查看成绩，遇到一道题目，题目表述如下：
给定汉诺塔问题中的 4 个圆盘，递归算法最多调用同一个函数 ___ 次。
A. 10
B. 16
C.22
D.31
我唯一知道的是我选了B.16，我错了。
上网查了下发现应该是2n - 1次，也就是15次。
但是，它不在选项中。
哪个选项是正确的？
任何建议将不胜感激。
谢谢。
4 盘拼图需要 15 步。不过，递归调用的次数取决于它的实现方式。
如果您的递归基本情况是 1 个磁盘 => 1 次移动，那么它是 15。如果您的递归基本情况是 0 个磁盘 => 0 次移动，那么它是 31。