cyberangles blog

Time Complexity Analysis | Tower Of Hanoi (Recursion)

The Tower of Hanoi is a classic problem in computer science and mathematics. It involves moving a stack of disks from one peg to another, with the constraint that a larger disk cannot be placed on top of a smaller one. In this blog, we will analyze the time complexity of the recursive solution for the Tower of Hanoi problem. We'll also look at common practices, best practices, and provide example usage.

2026-07

Table of Contents#

  1. Problem Statement
  2. Recursive Solution
  3. Time Complexity Analysis
  4. Common Practices
  5. Best Practices
  6. Example Usage
  7. References

1. Problem Statement#

The Tower of Hanoi consists of three pegs (let's call them A, B, and C) and a number of disks of different sizes. Initially, all the disks are stacked on one peg (say peg A) in such a way that each disk is smaller than the one below it. The goal is to move the entire stack of disks from peg A to peg C, using peg B as an auxiliary, while following the rule that a larger disk cannot be placed on top of a smaller disk.

2. Recursive Solution#

Here is the Python code for the recursive solution of the Tower of Hanoi problem:

def tower_of_hanoi(n, source, auxiliary, destination):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, source, destination)

In this code, the function tower_of_hanoi takes four parameters: n (the number of disks), source (the peg from which we are moving the disks), auxiliary (the auxiliary peg), and destination (the peg to which we are moving the disks). The base case is when n = 1, in which case we simply move the single disk. For n > 1, we first move n - 1 disks from the source to the auxiliary using the destination as the auxiliary, then move the largest disk from the source to the destination, and finally move the n - 1 disks from the auxiliary to the destination using the source as the auxiliary.

3. Time Complexity Analysis#

Let's denote the time complexity of the tower_of_hanoi function with T(n).

  • Base Case: When n = 1, the function makes a constant number of operations (a single print statement). So, T(1) = O(1).
  • Recursive Case: For n > 1, the function makes two recursive calls to tower_of_hanoi with n - 1 disks each. The time taken for these recursive calls is 2T(n - 1). Additionally, there is a constant amount of work (the print statement for moving the largest disk). So, the recurrence relation is T(n) = 2T(n - 1) + O(1).

To solve this recurrence relation, we can expand it:

[ \begin{align*} T(n)&=2T(n - 1)+1\ &=2(2T(n - 2)+1)+1\ &=2^2T(n - 2)+2 + 1\ &=2^3T(n - 3)+2^2+2 + 1\ &\cdots\ &=2^{n - 1}T(1)+2^{n - 2}+2^{n - 3}+\cdots+2 + 1 \end{align*} ]

Since T(1) = O(1), and the sum of the geometric series 2^{n - 2}+2^{n - 3}+\cdots+2 + 1 is 2^{n - 1}-1. So, T(n)=2^{n}-1.

In big - O notation, the time complexity of the recursive Tower of Hanoi solution is O(2^n). This is an exponential time complexity. As the number of disks n increases, the number of operations grows very rapidly.

4. Common Practices#

  • Understanding the Recursive Structure: It is common to first understand how the recursive calls are made and how the problem is broken down into smaller sub - problems. In the Tower of Hanoi, each recursive call reduces the problem size by one.
  • Visualizing the Problem: Many people find it helpful to visualize the movement of disks for small values of n (e.g., n = 2 or n = 3) to understand the overall process.

5. Best Practices#

  • Using Iterative Approaches for Optimization: Since the recursive solution has an exponential time complexity, for large values of n, it may not be practical. There are iterative algorithms for the Tower of Hanoi problem that can be more efficient in terms of space (although the time complexity remains the same). However, understanding the recursive solution is fundamental for building an understanding of recursion.
  • Analyzing Time Complexity Early: When designing algorithms, especially recursive ones, it is a best practice to analyze the time complexity early. This helps in determining the scalability of the algorithm.

6. Example Usage#

Let's call the tower_of_hanoi function with n = 3:

tower_of_hanoi(3, 'A', 'B', 'C')

The output will be:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

7. References#

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison - Wesley Professional.