More Recursion Adventures

Real-world analogy

What is it?

This lesson explores more recursion patterns: Fibonacci sequences, power calculations, and the famous Tower of Hanoi puzzle. You'll see when recursion is elegant and clean, when it can be slow, and learn the first hints of how to make it faster. These patterns appear everywhere in competitive programming!

Real-world relevance

Fibonacci numbers appear in nature — the spiral of sunflower seeds, the branching of trees, and the shell of a nautilus all follow Fibonacci patterns. The Tower of Hanoi was invented in 1883 and is used to teach recursion worldwide. Fast power calculation is used in cryptography to keep your online passwords safe!

Key points

• Fibonacci with Recursion — The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21... Each number is the sum of the two before it. With recursion: fib(n) = fib(n-1) + fib(n-2). Base cases: fib(0) = 0 and fib(1) = 1. It's beautiful but can be slow for big numbers!
• Why Recursive Fibonacci is Slow — Recursive Fibonacci recalculates the same values many times. fib(5) calls fib(4) and fib(3). But fib(4) also calls fib(3). So fib(3) is calculated TWICE! For fib(40), millions of repeated calculations happen. This is why we sometimes need smarter approaches.
• Power with Recursion — To calculate base^exp: power(2, 5) = 2 × power(2, 4) = 2 × 2 × power(2, 3)... Base case: power(base, 0) = 1 (anything to the power 0 is 1). This is clean and elegant — each call reduces the exponent by 1.
• Fast Power (Divide and Conquer) — There's a faster way! If exp is even: power(base, exp) = power(base, exp/2) × power(base, exp/2). If exp is odd: base × power(base, exp-1). This cuts the work in half each time! power(2, 8) only needs 4 calls instead of 8.
• Tower of Hanoi — A classic puzzle: Move n disks from peg A to peg C, using peg B as helper. Rules: only move one disk at a time, never put a bigger disk on a smaller one. The recursive solution: move n-1 disks to helper, move the biggest disk to target, then move n-1 disks from helper to target.
• Counting with Recursion — You can count things recursively too. How many digits does a number have? countDigits(n) = 1 + countDigits(n/10). Base case: if n < 10, it has 1 digit. countDigits(1234) = 1 + countDigits(123) = 1 + 1 + countDigits(12) = 1 + 1 + 1 + countDigits(1) = 4.
• Printing Patterns with Recursion — Recursion can print cool patterns. Print numbers 1 to n: first call printUp(n-1) to print 1 to n-1, then print n. Print numbers n to 1: first print n, then call printDown(n-1). The order of the recursive call and the print statement matters!
• When to Use Recursion vs Loops — Use recursion when the problem naturally breaks into smaller versions of itself (trees, divide and conquer, backtracking). Use loops when you're just counting or iterating through a list. In competitive programming, recursion is essential for many advanced algorithms.
• Memoization Preview — The fix for slow recursive Fibonacci is called 'memoization' — saving results so you don't recalculate them. Store fib(n) in an array the first time you calculate it. Next time you need it, just look it up! This turns slow recursion into fast recursion. You'll master this in dynamic programming!

Code example

#include <bits/stdc++.h>
using namespace std;

// Fibonacci (simple recursive)
int fib(int n) {
    if (n <= 0) return 0;  // Base case 1
    if (n == 1) return 1;  // Base case 2
    return fib(n - 1) + fib(n - 2);  // Two recursive calls!
}

// Fast power using recursion
long long fastPow(long long base, int exp) {
    if (exp == 0) return 1;  // Base case
    if (exp % 2 == 0) {
        long long half = fastPow(base, exp / 2);
        return half * half;  // Even: square the half
    }
    return base * fastPow(base, exp - 1);  // Odd: reduce by 1
}

// Tower of Hanoi
void hanoi(int n, char from, char to, char helper) {
    if (n == 0) return;  // Base case: no disks to move
    hanoi(n - 1, from, helper, to);  // Move n-1 to helper
    cout << "Move disk " << n << " from " << from << " to " << to << "\n";
    hanoi(n - 1, helper, to, from);  // Move n-1 from helper to target
}

int main() {
    // Fibonacci
    cout << "Fibonacci sequence: ";
    for (int i = 0; i < 10; i++) cout << fib(i) << " ";
    cout << "\n";  // 0 1 1 2 3 5 8 13 21 34
    
    // Fast power
    cout << "2^10 = " << fastPow(2, 10) << "\n";  // 1024
    
    // Tower of Hanoi with 3 disks
    cout << "Tower of Hanoi (3 disks):\n";
    hanoi(3, 'A', 'C', 'B');
    return 0;
}

Line-by-line walkthrough

1. 1. #include and using namespace std; — our standard setup for competitive programming.
2. 2. int fib(int n) — the Fibonacci function takes a number n and returns the nth Fibonacci number.
3. 3. if (n <= 0) return 0; if (n == 1) return 1; — TWO base cases! Fibonacci needs two because each call depends on TWO previous values. fib(0)=0 and fib(1)=1 are the starting points.
4. 4. return fib(n-1) + fib(n-2); — the recursive case calls fib TWICE: once for n-1 and once for n-2. This is what makes it slow for large n — it branches into two calls each time!
5. 5. long long fastPow(long long base, int exp) — fast power uses long long because powers can get very large very quickly.
6. 6. if (exp == 0) return 1; — base case: anything to the power 0 is 1.
7. 7. if (exp % 2 == 0) — if the exponent is even, we can be clever: calculate the half-power once and square it. This is much faster than multiplying one at a time!
8. 8. long long half = fastPow(base, exp/2); return half * half; — we only make ONE recursive call and then square the result. This halves the work each time!
9. 9. void hanoi(int n, char from, char to, char helper) — the Tower of Hanoi function takes: how many disks, which peg they're on, which peg to move to, and which peg to use as a helper.
10. 10. The hanoi function: move n-1 disks to helper, move the biggest disk to target, then move n-1 disks from helper to target. It's beautifully simple once you trust the recursion!

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(6) << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Fibonacci Sequence Explained (Numberphile)
• Tower of Hanoi — Step by Step (GeeksforGeeks)
• Recursion Problems on CSES (CSES Problem Set)