In the recursive solution to the Towers of Hanoi problem,the number of disks to move ______ at each recursive call.
A)decreases by 1
B)increases by 1
C)decreases by half
D)increases by half

Question

Quizplus · Accepted Answer

In the Towers of Hanoi problem, we have to move all the disks from one pole to another. To move n disks from a source pole to a destination pole, we have to first move n-1 disks from the source pole to the auxiliary pole. After that, we can move the largest disk from the source pole to the destination pole, and then move the n-1 disks from the auxiliary pole to the destination pole. This process is repeated recursively until all the disks are moved to the destination pole. As we can see, the number of disks to move decreases by 1 at each recursive call.

In the Recursive Solution to the Towers of Hanoi Problem,the