---
title: "Recursion, Fibonacci and TOH"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:recursion-fibonacci-toh"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recursion-fibonacci-toh
site: BCT Engineering
---

# Recursion, Fibonacci and TOH

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2068 Bhadra, 8 marks
- Video: [Tower of Hanoi Problem - Made Easy](https://www.youtube.com/watch?v=q6RicK1FCUs) — Abdul Bari
- 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/recursion-fibonacci-toh
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

Define recursion. Which algorithm would you prefer between iterative and recursive for the Fibonacci sequence and why? Discuss TOH problem and its solution.

## Short answer

Recursion is a function calling itself with smaller input until a base case. Iterative Fibonacci is preferred because recursive recomputes values, O(2^n) time and O(n) stack, while iterative is O(n) time and O(1) space. Tower of Hanoi moves n-1 disks to auxiliary, largest to target, then n-1 to target; moves = 2^n - 1.

## Answer

#### Recursion
**Recursion** is a method where a function calls itself with smaller input until a base case is reached. Each call keeps its own parameters and local variables on the stack. A recursive function needs (1) a base case and (2) a recursive case that moves toward the base case.

#### Iterative or recursive for Fibonacci?
I prefer the **iterative** algorithm.

```c
int fibr(int n) { return n <= 1 ? n : fibr(n-1) + fibr(n-2); }   /* recursive */

int fibi(int n) {                                                /* iterative */
    int a = 0, b = 1, c;
    if (n == 0) return 0;
    for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; }
    return b;
}
```
Reasons:
- The recursive version recomputes the same values many times: fib(5) makes 15 calls and fib(30) makes 2,692,537 calls (counted by program), so time is exponential O(2ⁿ).
- Recursion uses O(n) stack space; the loop uses O(1).
- The iterative version takes only n steps, O(n).

```text
              fib(4)
            /        \
        fib(3)       fib(2)
        /    \       /    \
    fib(2) fib(1) fib(1) fib(0)
    /   \
 fib(1) fib(0)        fib(2) is computed twice
```

#### Tower of Hanoi
Three pegs A, B, C and n disks on A (largest at bottom). Move all to C, one disk at a time, never putting a larger disk on a smaller one.

Solution: move n-1 disks A→B (using C), move disk n A→C, move n-1 disks B→C (using A).
```c
void toh(int n, char from, char to, char aux) {
    if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); return; }
    toh(n-1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    toh(n-1, aux, to, from);
}
```
Moves needed = 2ⁿ − 1. For n = 3: A→C, A→B, C→B, A→C, B→A, B→C, A→C (7 moves). TOH is a case where recursion is preferred because the iterative solution is much harder to write.

## Check yourself

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

1. Why is iterative Fibonacci preferred?
   A. Recursive version is O(1)
   B. Recursive version recomputes values giving O(2^n) time, loop is O(n)
   C. Loop uses O(n) stack
   D. Recursion cannot compute Fibonacci
   Answer: B. Repeated subproblems cause exponential calls, e.g. fib(30) makes 2,692,537 calls. (Key point: Why iterative Fibonacci)

2. What are the space needs of recursive vs iterative Fibonacci?
   A. Recursive O(1); iterative O(n)
   B. Both O(n)
   C. Recursive O(n) stack; iterative O(1)
   D. Both O(1)
   Answer: C. Recursion depth n needs n frames; the loop uses a few variables. (Key point: Space)

3. What is the TOH solution for n disks A to C?
   A. disk n A to B, then rest to C
   B. all disks directly to C
   C. n-1 disks A to C, disk n A to B
   D. n-1 disks A to B, disk n A to C, n-1 disks B to C
   Answer: D. Smaller tower goes out of the way, largest moves, then smaller tower returns on top. (Key point: TOH solution)

4. How many moves for 3 disks, and why is recursion preferred for TOH?
   A. 7; iterative solution is much harder to write
   B. 8; recursion is faster
   C. 7; recursion uses no stack
   D. 6; loops cannot count
   Answer: A. 2^3 - 1 = 7 and the problem is naturally recursive. (Key point: TOH moves and preference)

## Related in Data Structure and Algorithm

- [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
- [Recursion; iterative vs recursive choice](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adefine-recursion-iterative-vs-recursive) — 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×
- [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×
- [Prefer O(n) or O(log n) algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aprefer-on-or-ologn) — Data Structure and Algorithm, chapter 9
- [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

## Related in other subjects

- [Recursive/iterative query and DNS records](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Adns-recursive-iterative-records) — Computer Networks and Security, chapter 6