---
title: "TOH for 3 disks and recursion principle"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:toh-3-disks-tree-principle"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-3-disks-tree-principle
site: BCT Engineering
---

# TOH for 3 disks and recursion principle

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2073 Magh, 6+2 marks
- Video: [Towers of Hanoi as an Example of Recursion](https://www.youtube.com/watch?v=Ajy8XweC3L8) — TutorialsPoint
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/toh-3-disks-tree-principle
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

Explain a Tower of Hanoi for 3 disks and also generate recursion tree. Explain the basic principle of recursion with example.

## Short answer

For three disks, TOH(3,A,C,B) produces moves A->C, A->B, C->B, A->C, B->A, B->C, A->C, with calls=7=2^3-1. The recursion tree has root TOH(3,A,C,B) with two TOH(2) subtrees, and in-order traversal prints the moves. Basic recursion principle: solve a smaller instance plus a base case, e.g. fact(n)=n*fact(n-1) with fact(0)=1.

## Answer

#### Tower of Hanoi for 3 disks
Pegs A (source), B (auxiliary), C (destination). Three disks, 1 (smallest) to 3 (largest), are on A. Rules: move one disk at a time, take only the top disk, never place a larger disk on a smaller one. Solution = TOH(3, A, C, B), where TOH(n, from, to, aux) does: TOH(n-1, from, aux, to); move disk n from→to; TOH(n-1, aux, to, from).

| Move | Disk | From | To | Pegs after the move (A / B / C) |
|---|---|---|---|---|
| 1 | 1 | A | C | 3,2 / - / 1 |
| 2 | 2 | A | B | 3 / 2 / 1 |
| 3 | 1 | C | B | 3 / 2,1 / - |
| 4 | 3 | A | C | - / 2,1 / 3 |
| 5 | 1 | B | A | 1 / 2 / 3 |
| 6 | 2 | B | C | 1 / - / 3,2 |
| 7 | 1 | A | C | - / - / 3,2,1 |

#### Recursion tree
```text
                    TOH(3,A,C,B)
                  [4: disk 3 A->C]
              /                      \
     TOH(2,A,B,C)                TOH(2,B,C,A)
    [2: disk 2 A->B]            [6: disk 2 B->C]
      /         \                 /         \
 (1,A,C,B)   (1,C,B,A)      (1,B,A,C)   (1,A,C,B)
 [1: A->C]   [3: C->B]      [5: B->A]   [7: A->C]
```
Moves are printed in in-order (left subtree, node, right subtree): 1 to 7.

Calls = 7, moves = 7 = 2³ − 1.

#### Basic principle of recursion
A problem is solved by expressing it in terms of a **smaller instance of the same problem**, plus a **base case** that is solved directly. Every recursive call must move closer to the base case, otherwise it never stops.

Example: factorial
- Base case: `fact(0) = 1`
- Recursive case: `fact(n) = n × fact(n-1)`

```c
int fact(int n) { return (n == 0) ? 1 : n * fact(n - 1); }
```
`fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 6`. The calls are stored on the stack and are resolved in reverse order when the base case returns.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which rule is part of TOH?
   A. Move two disks at once
   B. Never place a larger disk on a smaller one
   C. Move any disk from any position
   D. Use only two pegs
   Answer: B. Only one top disk moves at a time and never larger on smaller. (Key point: Rule)

2. In TOH(3, A, C, B), what are A, C, B?
   A. A destination, C source, B auxiliary
   B. A source, C auxiliary, B destination
   C. A source, C destination, B auxiliary
   D. All are destinations
   Answer: C. The call form is TOH(n, from, to, aux). (Key point: Roles of pegs)

3. What is the basic principle of recursion?
   A. Repeat a block with a counter
   B. Store all results in an array
   C. Avoid parameters
   D. Express the problem via a smaller instance of itself plus a directly solved base case
   Answer: D. Calls must move closer to the base case. (Key point: Basic principle)

4. fact(3) = 3 x fact(2) = 3 x 2 x fact(1) = 3 x 2 x 1 x fact(0). What is the base case value and result?
   A. fact(0) = 1 and result 6
   B. fact(0) = 0 and result 0
   C. fact(0) = 1 and result 3
   D. fact(1) = 0 and result 6
   Answer: A. Base case fact(0) = 1, so 3 x 2 x 1 x 1 = 6. (Key point: Factorial trace)

## Related in Data Structure and Algorithm

- [Recursion tree for Tower of Hanoi, 4 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-recursion-tree-4-disks) — Data Structure and Algorithm, chapter 5
- [Tree recursion and TOH with n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atree-recursion-toh-algorithm) — Data Structure and Algorithm, chapter 5
- [Box trace and TOH recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abox-trace-toh-tree) — Data Structure and Algorithm, chapter 5
- [TOH algorithm and recursion tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-algorithm-recursion-tree) — Data Structure and Algorithm, chapter 5, asked 2×
- [Solve TOH for 3 disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-steps) — Data Structure and Algorithm, chapter 5, asked 2×
- [Recursion properties, Fibonacci, TOH algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-properties-fibonacci-toh) — Data Structure and Algorithm, chapter 5

## Related in other subjects

- [Set up recurrence for Tower of Hanoi](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-setup-recurrence) — Discrete Structure, chapter 3
- [Derive and solve Tower of Hanoi recurrence](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahanoi-derive-and-solve) — Discrete Structure, chapter 3