Recursion

What is Recursion?

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution has two essential parts:

Base case — the condition that stops the recursion (prevents infinite loop)
Recursive case — the function calls itself with a smaller/simpler input

Each recursive call is pushed onto the call stack. When the base case is reached, the stack unwinds and results are returned back up the chain.

Recursion vs Iteration

Aspect	Recursion	Iteration
Code clarity	Often cleaner for tree/graph problems	Cleaner for simple loops
Memory	O(n) stack space per call depth	O(1) typically
Speed	Slower (function call overhead)	Faster
Stack overflow risk	Yes — deep recursion can overflow	No
Best for	Trees, graphs, divide & conquer, backtracking	Simple loops, performance-critical code

Tail Recursion

Tail recursion is when the recursive call is the last operation in the function. Some compilers/runtimes optimize tail calls to avoid growing the stack (tail call optimization — TCO). Python does NOT support TCO; C++ and Java compilers may optimize it.

Factorial and Fibonacci (Naive + Memoized)

#include <iostream>
#include <unordered_map>
using namespace std;

// Factorial — O(n) time, O(n) space (call stack)
long long factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

// Fibonacci naive — O(2^n) time — very slow!
int fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// Fibonacci memoized — O(n) time, O(n) space
unordered_map<int, long long> memo;
long long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

int main() {
    cout << "5! = " << factorial(5) << endl;       // 120
    cout << "10! = " << factorial(10) << endl;     // 3628800
    cout << "fib(10) naive = " << fibNaive(10) << endl;  // 55
    cout << "fib(40) memo = " << fibMemo(40) << endl;    // 102334155
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class Recursion {

    // Factorial — O(n) time, O(n) space
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    // Fibonacci naive — O(2^n) time
    static int fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Fibonacci memoized — O(n) time
    static Map<Integer, Long> memo = new HashMap<>();
    static long fibMemo(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        long result = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));          // 120
        System.out.println("10! = " + factorial(10));        // 3628800
        System.out.println("fib(10) = " + fibNaive(10));     // 55
        System.out.println("fib(40) = " + fibMemo(40));      // 102334155
    }
}

from functools import lru_cache

# Factorial — O(n) time, O(n) space
def factorial(n):
    if n <= 1: return 1       # base case
    return n * factorial(n - 1)  # recursive case

# Fibonacci naive — O(2^n) time — very slow!
def fib_naive(n):
    if n <= 1: return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Fibonacci memoized with dict — O(n) time
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n in memo: return memo[n]
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Fibonacci with @lru_cache decorator — cleanest approach
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

print(f"5! = {factorial(5)}")          # 120
print(f"10! = {factorial(10)}")        # 3628800
print(f"fib(10) = {fib_naive(10)}")   # 55
print(f"fib(40) = {fib(40)}")         # 102334155

// Factorial — O(n) time, O(n) space
function factorial(n) {
    if (n <= 1) return 1;           // base case
    return n * factorial(n - 1);    // recursive case
}

// Fibonacci naive — O(2^n) time
function fibNaive(n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// Fibonacci memoized — O(n) time
function fibMemo(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.set(n, result);
    return result;
}

console.log("5! =",    factorial(5));       // 120
console.log("10! =",   factorial(10));      // 3628800
console.log("fib(10) =", fibNaive(10));     // 55
console.log("fib(40) =", fibMemo(40));      // 102334155

Tower of Hanoi

Tower of Hanoi is a classic recursion problem: move n disks from source peg to destination peg using an auxiliary peg, never placing a larger disk on a smaller one. It requires 2^n - 1 moves — O(2^n) time.

Tower of Hanoi

#include <iostream>
using namespace std;

// Tower of Hanoi — O(2^n) moves
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);   // move n-1 disks to aux
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from);   // move n-1 disks from aux to dest
}

int main() {
    int n = 3;
    cout << "Tower of Hanoi with " << n << " disks:" << endl;
    hanoi(n, 'A', 'C', 'B');
    // Total moves = 2^n - 1 = 7
    return 0;
}

public class TowerOfHanoi {

    static void hanoi(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        hanoi(n - 1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        hanoi(n - 1, aux, to, from);
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println("Tower of Hanoi with " + n + " disks:");
        hanoi(n, 'A', 'C', 'B');
        // Total moves = 2^n - 1 = 7
    }
}

def hanoi(n, from_peg, to_peg, aux_peg):
    if n == 1:
        print(f"Move disk 1 from {from_peg} to {to_peg}")
        return
    hanoi(n - 1, from_peg, aux_peg, to_peg)   # move n-1 to aux
    print(f"Move disk {n} from {from_peg} to {to_peg}")
    hanoi(n - 1, aux_peg, to_peg, from_peg)   # move n-1 from aux to dest

n = 3
print(f"Tower of Hanoi with {n} disks:")
hanoi(n, 'A', 'C', 'B')
# Total moves = 2^n - 1 = 7

function hanoi(n, from, to, aux) {
    if (n === 1) {
        console.log(`Move disk 1 from ${from} to ${to}`);
        return;
    }
    hanoi(n - 1, from, aux, to);   // move n-1 to aux
    console.log(`Move disk ${n} from ${from} to ${to}`);
    hanoi(n - 1, aux, to, from);   // move n-1 from aux to dest
}

const n = 3;
console.log(`Tower of Hanoi with ${n} disks:`);
hanoi(n, 'A', 'C', 'B');
// Total moves = 2^n - 1 = 7

Previous Next

Recursion

What is Recursion?

Recursion vs Iteration

Tail Recursion

Tower of Hanoi

Ready to Level Up Your Skills?