Алгоритм анализа - рекуррентное уравнение (Ханойская башня)

Question

Я видел этот рекурсивный алгоритм для решения Ханойской башни в Википедии. Может ли кто-нибудь объяснить мне, как я получаю уравнение повторения этого алгоритма?

Рекурсивное решение

• пометьте колышки A, B, C - эти ярлыки могут перемещаться на разных этапах
• пусть n будет общим количеством дисков
• нумерация дисков от 1 (самый маленький, самый верхний) до n (самый большой, самый нижний)

Чтобы переместить n дисков из колышка A в колышек C:

• переместить n−1 дисков из A в B. Это оставит диск n на колышке A
• переместить диск n из A в C
• переместить n−1 дисков из B в C, чтобы они находились на диске n

Выше приведен рекурсивный алгоритм, для выполнения шагов 1 и 3 снова примените тот же алгоритм для n−1. Вся процедура представляет собой конечное число шагов, так как в какой-то момент алгоритм будет необходим для n = 1. Этот шаг, перемещение одного диска из колышка A в колышек B, тривиален.

Answer 1

Первые три шага могут быть выполнены за линейное время, вторые три шага являются рекурсивной частью, затем просто пишите в рекурсивном формате то, что написано в текстовом формате:

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

С другой стороны, поскольку метки не важны и T(n,A,B) = T(n,B,C)=T(n,A,C)=..., мы можем избавиться от меток, поэтому уравнение будет?