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

# Recursion properties, Fibonacci, TOH algorithm

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2068 Magh, 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-properties-fibonacci-toh
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

State properties of recursion. Why is the recursive method for Fibonacci sequence not preferred? Write an algorithm for TOH problem and use it to find the solution for three disks.

## Short answer

Properties: self-call, base case, smaller subproblem, stack frames, results combined while returning. Recursive Fibonacci is not preferred because it repeats subproblems: fib(30) makes 2,692,537 calls, O(2^n) time and O(n) stack. TOH for three disks: A->C, A->B, C->B, A->C, B->A, B->C, A->C, total 7 moves.

## Answer

#### Properties of recursion
1. A recursive function calls itself, directly or indirectly.
2. It has a **base case** (stopping condition) whose answer is known without further calls.
3. Each recursive call works on a **smaller or simpler** version of the problem and moves toward the base case.
4. Every call has its own parameters, local variables and return address, stored on the **stack**.
5. The result is built while returning (unwinding) from the calls.
6. Without a reachable base case the recursion is infinite and ends in stack overflow.

#### Why recursive Fibonacci is not preferred
`fib(n) = fib(n-1) + fib(n-2)`, `fib(0) = 0`, `fib(1) = 1`. The same sub-problems are solved again and again: in fib(5), fib(3) is computed twice and fib(2) three times. The number of calls grows exponentially (fib(5): 15 calls, fib(30): 2,692,537 calls, counted by program), time is O(2ⁿ), and stack depth is n. An iterative loop gives the answer in n steps with constant memory.

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

#### Solution for 3 disks: TOH(3, A, C, B)
| 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 |

Total 2³ − 1 = 7 moves.

## Check yourself

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

1. Which is a property of recursion?
   A. It never uses the stack
   B. It has a base case with a known answer and each call works on a smaller problem
   C. It always runs faster than a loop
   D. It needs no stopping condition
   Answer: B. A base case and progress toward it are essential. (Key point: Base case property)

2. What happens without a reachable base case?
   A. The function returns 0
   B. The compiler adds one
   C. Infinite recursion ending in stack overflow
   D. It becomes a loop
   Answer: C. Calls never stop and the stack fills. (Key point: Without base case)

3. In fib(5), why is the recursive method inefficient?
   A. It never reaches fib(0)
   B. Results are stored twice
   C. It uses floating point
   D. Same sub-problems are recomputed, e.g. fib(3) twice and fib(2) three times
   Answer: D. Repeated work gives exponential O(2^n) time; fib(5) makes 15 calls. (Key point: Fibonacci repeated work)

4. In TOH(n, from, to, aux), which is the correct third step?
   A. TOH(n-1, aux, to, from)
   B. TOH(n-1, from, aux, to)
   C. TOH(n-1, to, from, aux)
   D. Move disk 1 from to
   Answer: A. After moving disk n, the n-1 disks move from aux to the destination using the source as helper. (Key point: TOH algorithm)

## Related in Data Structure and Algorithm

- [Recursion, Fibonacci and TOH](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-fibonacci-toh) — 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×
- [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
- [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
- [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×

## Related in other subjects

- [Multipath inheritance problem and solution](https://www.bctengineer.com/question.md?key=semester_3%2Fobject_oriented_programming%3Amultipath-inheritance-problem) — Object Oriented Programming, chapter 6, asked 2×
- [Recursive language and its properties](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-language-properties) — Theory of Computation, chapter 4, asked 2×