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

# Tree recursion and TOH with n disks

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2074 Bhadra, 1+3+4 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/tree-recursion-toh-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

What is tree recursion? Write an algorithm for TOH with n disks and generate a recursion tree of TOH problem with 3 disks.

## Short answer

Tree recursion makes more than one recursive call per invocation, forming a call tree, as in Fibonacci and TOH. TOH algorithm: if n=1 move disk; else TOH(n-1,from,aux,to), move disk n, TOH(n-1,aux,to,from). For 3 disks the recursion tree has root TOH(3,A,C,B) and two TOH(2) subtrees; moves are printed in in-order, 7 calls.

## Answer

#### Tree recursion
A recursive function that makes **more than one recursive call** in its body is tree recursive, because the calls form a tree. Examples: Fibonacci `fib(n-1) + fib(n-2)` and Tower of Hanoi (two calls for n-1 disks). Linear recursion (one call, like factorial) forms a chain instead.

#### Algorithm TOH(n, from, to, aux)
1. If n = 1: move disk 1 from `from` to `to`; return.
2. TOH(n-1, from, aux, to).
3. Move disk n from `from` to `to`.
4. TOH(n-1, aux, to, from).

```c
#include <stdio.h>

/* move n disks from 'from' to 'to' using 'aux' */
void toh(int n, char from, char to, char aux) {
    if (n == 1) {                                   /* base case */
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    toh(n - 1, from, aux, to);                      /* step 1 */
    printf("Move disk %d from %c to %c\n", n, from, to);   /* step 2 */
    toh(n - 1, aux, to, from);                      /* step 3 */
}

int main(void) {
    toh(3, 'A', 'C', 'B');
    return 0;
}
```

#### Recursion tree for 3 disks, call TOH(3, A, C, B)
```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.

Move sequence (verified by running the algorithm):

| 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 |

Calls = 2³ − 1 = 7, tree depth = 3, moves = 7.

## Check yourself

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

1. What defines tree recursion?
   A. Only one recursive call
   B. More than one recursive call in the body
   C. A call from main
   D. Calls using pointers
   Answer: B. Multiple calls make the call structure a tree; one call gives a chain (linear recursion). (Key point: Tree recursion)

2. Which pair is tree recursive?
   A. Factorial and sum
   B. Factorial and Fibonacci
   C. Fibonacci and Tower of Hanoi
   D. Sum and TOH
   Answer: C. Fibonacci makes two calls and TOH makes two calls; factorial makes one. (Key point: Examples)

3. In what order are moves produced from the TOH tree?
   A. Pre-order
   B. Post-order
   C. Random
   D. In-order (left subtree, node, right subtree)
   Answer: D. The move is printed between the two recursive calls. (Key point: Move order)

4. For 3 disks, how many calls and tree depth?
   A. 7 calls, depth 3
   B. 8 calls, depth 3
   C. 7 calls, depth 7
   D. 3 calls, depth 7
   Answer: A. Calls = 2^3 - 1 = 7, depth = n = 3. (Key point: Counts for 3 disks)

## Related in Data Structure and Algorithm

- [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×
- [TOH for 3 disks and recursion principle](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-3-disks-tree-principle) — Data Structure and Algorithm, chapter 5
- [TOH problem with solution for n disks](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atoh-n-disks-solution) — 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
- [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
- [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