Recursion — The Magic of Self-Calling Functions

Real-world analogy

What is it?

Recursion is a technique where a function solves a problem by calling itself with a smaller version of the same problem. Every recursive function needs a base case (when to stop) and a recursive case (how to make the problem smaller). It's like solving a big puzzle by breaking it into identical smaller puzzles.

Real-world relevance

Recursion appears everywhere! File systems use recursion (folders inside folders inside folders). Google's search algorithm uses recursion to crawl web pages. Family trees are recursive (you have parents, who have parents, who have parents...). Even Russian nesting dolls and fractal art are recursive patterns!

Key points

• What is Recursion? — Recursion is when a function calls ITSELF. It sounds crazy, but it's one of the most powerful ideas in programming. Instead of using a loop, the function keeps calling itself with a simpler version of the problem until it reaches a stopping point.
• The Base Case — When to STOP — The base case is the MOST IMPORTANT part of recursion. It tells the function when to stop calling itself. Without a base case, the function would call itself forever (infinite recursion) and your program would crash. Think of it as the smallest nesting doll — no more dolls inside!
• The Recursive Case — Making Progress — The recursive case is where the function calls itself with a SIMPLER or SMALLER input. For example, to calculate 5!, we say 5! = 5 × 4!, and then 4! = 4 × 3!, and so on. Each call makes the problem smaller until we hit the base case.
• Factorial Example — Factorial of n (written n!) means multiplying all numbers from 1 to n. So 5! = 5 × 4 × 3 × 2 × 1 = 120. With recursion: factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) = ... = 5 × 4 × 3 × 2 × 1. The base case is factorial(0) = 1 or factorial(1) = 1.
• The Call Stack — A Stack of Plates — When a function calls itself, each call gets placed on the 'call stack' — like stacking plates. factorial(5) goes on, then factorial(4) on top, then factorial(3), etc. When the base case is reached, the plates start coming off one by one as each call returns its result.
• Sum of Numbers with Recursion — To add numbers from 1 to n: sum(n) = n + sum(n-1). sum(5) = 5 + sum(4) = 5 + 4 + sum(3) = 5 + 4 + 3 + sum(2) = 5 + 4 + 3 + 2 + sum(1) = 5 + 4 + 3 + 2 + 1 = 15. Base case: sum(1) = 1.
• Stack Overflow — Too Many Plates! — If you forget the base case or the problem doesn't get smaller, the function calls itself forever. The call stack gets too big and your program crashes with a 'stack overflow' error. Always make sure your recursion moves toward the base case!
• Recursion vs Loops — Anything you can do with recursion, you can also do with loops (and vice versa). Sometimes recursion makes code much cleaner and easier to understand. Other times, a simple loop is better. As you practice, you'll develop a feel for which to use.
• Thinking Recursively — The trick to recursion is: assume the function already works for smaller inputs, then figure out how to use that to solve the current input. For factorial: IF factorial(n-1) gives me the right answer, THEN factorial(n) = n × factorial(n-1). Trust the magic!

Code example

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

// Factorial using recursion
int factorial(int n) {
    if (n <= 1) return 1;  // Base case!
    return n * factorial(n - 1);  // Recursive case
}

// Sum from 1 to n using recursion
int sumTo(int n) {
    if (n == 1) return 1;  // Base case
    return n + sumTo(n - 1);  // Recursive case
}

int main() {
    cout << "5! = " << factorial(5) << "\n";  // 120
    cout << "Sum 1 to 10 = " << sumTo(10) << "\n";  // 55
    
    // Let's trace factorial(4):
    // factorial(4) = 4 * factorial(3)
    //              = 4 * 3 * factorial(2)
    //              = 4 * 3 * 2 * factorial(1)
    //              = 4 * 3 * 2 * 1
    //              = 24
    cout << "4! = " << factorial(4) << "\n";  // 24
    return 0;
}

Line-by-line walkthrough

1. 1. #include — includes all standard libraries so we can use cout, cin, and everything else we need.
2. 2. using namespace std; — lets us write cout instead of std::cout.
3. 3. int factorial(int n) — we define a function that takes a number n and returns its factorial. The return type is int.
4. 4. if (n <= 1) return 1; — this is the BASE CASE! When n is 0 or 1, we know the factorial is 1, so we return immediately without making another recursive call. This is what stops the recursion.
5. 5. return n * factorial(n - 1); — this is the RECURSIVE CASE. We multiply n by the factorial of (n-1). We trust that factorial(n-1) will give us the correct answer for the smaller problem.
6. 6. int sumTo(int n) — another recursive function that adds all numbers from 1 to n.
7. 7. if (n == 1) return 1; — base case for the sum function. The sum from 1 to 1 is just 1.
8. 8. return n + sumTo(n - 1); — recursive case: n plus the sum of all numbers from 1 to (n-1).
9. 9. In main(), we call factorial(5) which returns 120 (5×4×3×2×1) and sumTo(10) which returns 55 (1+2+3+...+10).

Spot the bug

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

int factorial(int n) {
    return n * factorial(n - 1);
}

int main() {
    cout << factorial(5) << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Recursion in 5 Minutes (Reducible)
• Recursion for Beginners (GeeksforGeeks)
• Recursion Practice Problems (Codeforces)