Recursion

Say you have to solve a big problem. But inside that big problem hides a smaller version of the exact same problem. And inside that, an even smaller one. So you do not write different code for each size. You write one function. It handles one small step, then asks itself to handle the rest. That trick is called recursion. Once it clicks, a lot of tree, search, and divide problems suddenly feel easy.

📚 What Is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem.

That sounds strange the first time. A function calling itself? Won’t that go on forever? No. Every good recursive function knows when to stop. It keeps shrinking the problem until the problem is so tiny that the answer is obvious. Then it stops calling and starts returning.

So a recursive function always has two parts.

• Base case — the stopping point. The smallest input where you already know the answer. Here you do NOT call yourself again.
• Recursive case — you do a little bit of work. Then you call the same function on a smaller input.

If the recursive case never reaches the base case, the function calls itself forever. That is the one bug everyone hits early. We will talk about it soon.

🪆 A Real-World Analogy

Think of Russian nesting dolls. That is the wooden doll that opens up. Inside it sits a smaller doll. Inside that one sits an even smaller doll.

Now someone asks you “how many dolls are in here?” What do you do? You open one doll. Now you have the same question again, just with a smaller stack. So you open the next one. And the next. You keep doing the same action on a smaller and smaller stack.

When do you stop? You stop when you reach the tiny solid doll that does not open. That is your base case. That last doll is the moment you stop opening and start counting your way back out.

Recursion works the exact same way. Same action, smaller input, until you hit a stopping point.

🎯 Factorial: The Classic Example

Factorial of a number n is n multiplied by every whole number below it, all the way down to 1. We write it as n!.

So 5! = 5 × 4 × 3 × 2 × 1 = 120.

Now look at it closely. 5! is just 5 × 4!. And 4! is just 4 × 3!. See the pattern? The factorial of a number is that number times the factorial of the number below it. That is a smaller version of the same problem. Perfect for recursion.

Here is the rule in plain words.

• Base case: factorial of 0 (or 1) is 1. Stop here.
• Recursive case: factorial of n is n times factorial of n - 1.

Here is how you write factorial with recursion.

1. Check the base case first. If n is 0 or 1, return 1 right away.
2. If not, return n times the factorial of n - 1.
3. Each call makes n smaller. So in the end it reaches the base case and stops.

Here is factorial in all five languages.

#include <stdio.h>

// Returns the factorial of n using recursion
int factorial(int n) {
    if (n == 0 || n == 1)   // base case: stop here
        return 1;
    return n * factorial(n - 1);  // recursive case
}

int main() {
    printf("Factorial of 5 is %d\n", factorial(5));
    return 0;
}

Factorial of 5 is 120

#include <iostream>
using namespace std;

// Returns the factorial of n using recursion
int factorial(int n) {
    if (n == 0 || n == 1)   // base case: stop here
        return 1;
    return n * factorial(n - 1);  // recursive case
}

int main() {
    cout << "Factorial of 5 is " << factorial(5) << endl;
    return 0;
}

Factorial of 5 is 120

public class Factorial {
    // Returns the factorial of n using recursion
    static int factorial(int n) {
        if (n == 0 || n == 1)   // base case: stop here
            return 1;
        return n * factorial(n - 1);  // recursive case
    }

    public static void main(String[] args) {
        System.out.println("Factorial of 5 is " + factorial(5));
    }
}

Factorial of 5 is 120

# Returns the factorial of n using recursion
def factorial(n):
    if n == 0 or n == 1:        # base case: stop here
        return 1
    return n * factorial(n - 1)  # recursive case

print("Factorial of 5 is", factorial(5))

Factorial of 5 is 120

// Returns the factorial of n using recursion
function factorial(n) {
  if (n === 0 || n === 1)   // base case: stop here
    return 1;
  return n * factorial(n - 1);  // recursive case
}

console.log("Factorial of 5 is " + factorial(5));

Factorial of 5 is 120

🧱 How the Call Stack Works

When a function calls itself, the computer does not throw away the first call. It keeps it waiting. It needs to remember “I was in the middle of computing 5 × factorial(4), and I am still waiting for that answer.”

The place where the computer keeps all these waiting calls is the call stack. A call stack is a pile of paused function calls. The newest call sits on top. When a call finally returns a value, it is removed from the top. Then the call below it can continue.

Let us trace factorial(5). Each call waits for the smaller one below it.

The calls go down until they hit the base case. Then the answers come back up.

• factorial(1) returns 1.
• factorial(2) was waiting. Now it returns 2 × 1 = 2.
• factorial(3) returns 3 × 2 = 6.
• factorial(4) returns 4 × 6 = 24.
• factorial(5) returns 5 × 24 = 120.

So recursion goes two ways. First it goes deeper and deeper until the base case. Then it climbs back up, combining answers on the way. That down-then-up flow is the heart of how recursion really runs.

🐇 Fibonacci: When a Function Calls Itself Twice

The Fibonacci sequence is a list of numbers where each number is the sum of the two numbers before it. It starts 0, 1, 1, 2, 3, 5, 8, 13 and keeps going.

So how do you get the n-th Fibonacci number? You add the two before it. That is two smaller versions of the same problem, not one.

• Base case: Fibonacci of 0 is 0, and Fibonacci of 1 is 1. Stop here.
• Recursive case: Fibonacci of n is Fibonacci of n - 1 plus Fibonacci of n - 2.

Here is how you write Fibonacci with recursion.

1. If n is 0, return 0. If n is 1, return 1. These are the base cases.
2. Otherwise, return fib(n - 1) + fib(n - 2).
3. Each call splits into two smaller calls. Both of them reach a base case in the end.

Here is Fibonacci in all five languages. We print the 7th Fibonacci number.

#include <stdio.h>

// Returns the n-th Fibonacci number using recursion
int fib(int n) {
    if (n == 0)         // base case
        return 0;
    if (n == 1)         // base case
        return 1;
    return fib(n - 1) + fib(n - 2);  // two recursive calls
}

int main() {
    printf("Fibonacci of 7 is %d\n", fib(7));
    return 0;
}

Fibonacci of 7 is 13

#include <iostream>
using namespace std;

// Returns the n-th Fibonacci number using recursion
int fib(int n) {
    if (n == 0)         // base case
        return 0;
    if (n == 1)         // base case
        return 1;
    return fib(n - 1) + fib(n - 2);  // two recursive calls
}

int main() {
    cout << "Fibonacci of 7 is " << fib(7) << endl;
    return 0;
}

Fibonacci of 7 is 13

public class Fibonacci {
    // Returns the n-th Fibonacci number using recursion
    static int fib(int n) {
        if (n == 0)         // base case
            return 0;
        if (n == 1)         // base case
            return 1;
        return fib(n - 1) + fib(n - 2);  // two recursive calls
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci of 7 is " + fib(7));
    }
}

Fibonacci of 7 is 13

# Returns the n-th Fibonacci number using recursion
def fib(n):
    if n == 0:          # base case
        return 0
    if n == 1:          # base case
        return 1
    return fib(n - 1) + fib(n - 2)  # two recursive calls

print("Fibonacci of 7 is", fib(7))

Fibonacci of 7 is 13

// Returns the n-th Fibonacci number using recursion
function fib(n) {
  if (n === 0)        // base case
    return 0;
  if (n === 1)        // base case
    return 1;
  return fib(n - 1) + fib(n - 2);  // two recursive calls
}

console.log("Fibonacci of 7 is " + fib(7));

Fibonacci of 7 is 13

⚠️ The Bug Everyone Hits: Missing Base Case

What happens if you forget the base case? Or what if your recursive call never gets closer to the base case? Then the function keeps calling itself with no stopping point.

Remember the call stack. Every call gets stacked on top, waiting. If the calls never stop, the stack keeps growing until it runs out of room. The program then crashes with an error called stack overflow. A stack overflow is the error you get when the call stack grows too big for the memory the program is allowed to use.

Look at this broken factorial.

# BROKEN: no base case, this never stops
def factorial(n):
    return n * factorial(n - 1)   # always calls itself, forever

print(factorial(5))   # crashes with a stack overflow error

🔁 Recursion vs Iteration

Anything you can do with recursion you can also do with a loop. A loop is called iteration, which just means repeating with a loop instead of calling yourself. So which one should you use?

Here is the short comparison.

So the rule of thumb is simple. If the problem naturally breaks into smaller copies of itself, like trees, searching, or divide and conquer, then recursion reads beautifully. For plain repeating work, like adding up a list, a loop is usually simpler and lighter.

🧩 What You’ve Learned

• ✅ Recursion is a function calling itself to solve a smaller version of the same problem.
• ✅ Every recursive function needs a base case to stop and a recursive case to shrink the problem.
• ✅ The call stack keeps paused calls waiting. It goes deep to the base case, then climbs back up with answers.
• ✅ Factorial uses one recursive call. Fibonacci uses two.
• ✅ A missing or unreachable base case causes infinite recursion and a stack overflow crash.
• ✅ Iteration uses a loop instead. It is lighter for simple repeating tasks.

🚀 What’s Next?

• Divide and Conquer
• Binary Search: Iterative vs Recursive