Recurrence Relations · Recursive Algorithms

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Problem. It often happens that a computational problem can be reduced to itself. In such cases, the problem can naturally be solved using a recursive algorithm. A classic example is the “Tower of Hanoi” puzzle. In this puzzle, there are three rods, and \(n\) disks of increasing size are stacked on the first rod.

In each move, the top disk of one rod can be moved to another rod, but a larger disk cannot be placed on top of a smaller disk. What is the minimum number of moves required to transfer all the disks to another rod? Try it!

5 points