Recursion

Reviewed & published by Brayan K

Some problems are easiest to solve by solving a smaller copy of themselves — a function that calls itself. That's recursion, and once it clicks it becomes one of the most elegant tools in programming. By the end of this lesson you'll write recursive functions with a proper base case, trace how the call stack unwinds, and recognize when recursion beats a loop (and when it doesn't).

Part of the free C++ course at LearnCodingFast — hands-on lessons with worked examples and the output they print, plus practice exercises and a quick quiz.

What You'll Learn

• Write a function that calls itself
• Always include a base case to stop the recursion
• Move toward the base case in the recursive case
• Trace how the call stack grows and unwinds
• Apply recursion to factorial, Fibonacci, and power
• Recognize stack overflow and when to prefer a loop

💡 Real-World Analogy

Imagine standing in a long queue and wanting to know your position. You can't see the front, so you ask the person in front of you "what's your number?" — they don't know either, so they ask the person ahead of them, and so on. Eventually the question reaches the very first person (the base case), who says "I'm number 1". That answer travels back down the line, each person adding one, until it reaches you. That's recursion: each step delegates a smaller version of the question, and the answers flow back once the base case is hit.

📊 The Two Ingredients

Every recursive function needs both. Miss the base case and you get infinite recursion → stack overflow.

1. The Classic: Factorial

Factorial is the "hello world" of recursion. n! equals n times (n-1)!, and the chain stops at 1! = 1. Notice the two pieces: the base case (if (n <= 1) return 1;) that ends the recursion, and the recursive case that calls factorial with a smaller argument. Read the comment that traces how factorial(5) unfolds.

#include <iostream>
using namespace std;

// factorial(n) = n * (n-1) * (n-2) * ... * 1
long long factorial(int n) {
    if (n <= 1) return 1;          // BASE CASE: stops the recursion
    return n * factorial(n - 1);   // RECURSIVE CASE: smaller problem
}

int main() {
    cout << "5! = " << factorial(5) << endl;  // 5! = 120
    cout << "0! = " << factorial(0) << endl;  // 0! = 1
    cout << "7! = " << factorial(7) << endl;  // 7! = 5040

    // How 5! unfolds:
    // factorial(5) = 5 * factorial(4)
    //              = 5 * 4 * factorial(3)
    //              = 5 * 4 * 3 * factorial(2)
    //              = 5 * 4 * 3 * 2 * factorial(1)
    //              = 5 * 4 * 3 * 2 * 1  = 120
    return 0;
}

// ✅ Expected output:
//    5! = 120
//    0! = 1
//    7! = 5040

2. Recursion That Returns Nothing

Recursion isn't only for computing values — a void function can recurse to repeat an action. This countdown prints a number, then calls itself with n - 1 until it reaches the base case at 0. The key, as always: each call must move closer to the base case, or it never stops.

#include <iostream>
using namespace std;

// Print n, n-1, ... down to 1, then "Liftoff!".
void countdown(int n) {
    if (n == 0) {                  // BASE CASE
        cout << "Liftoff!" << endl;
        return;
    }
    cout << n << " ";              // do work
    countdown(n - 1);              // RECURSIVE CASE: move toward 0
}

int main() {
    countdown(5);
    // Output:  5 4 3 2 1 Liftoff!
    return 0;
}

// ✅ Expected output:
//    5 4 3 2 1 Liftoff!

Your turn. Complete the recursive case so sumTo(n) adds 1 + 2 + ... + n:

#include <iostream>
using namespace std;

// 🎯 YOUR TURN — sum 1 + 2 + ... + n recursively.
int sumTo(int n) {
    if (n <= 0) return 0;          // BASE CASE provided

    // RECURSIVE CASE: n plus the sum of everything below it.
    return ___;                    // 👉 n + sumTo(n - 1)
}

int main() {
    cout << sumTo(5) << endl;      // ✅ Expected: 15  (1+2+3+4+5)
    cout << sumTo(10) << endl;     // ✅ Expected: 55
    return 0;
}

🧩 Reorder Challenge

These lines form a complete recursive factorial function. Put them in the correct order:

A.     return n * factorial(n - 1);
B. int factorial(int n) {
C.     if (n <= 1) return 1;
D. }

Correct order: B → C → A → D

Open the function (B), check the base case first so recursion can terminate (C), then the recursive case multiplies by the smaller call (A), and close the brace (D). The base case must come before the recursive call.

3. Multiple Recursive Calls: Fibonacci

A recursive function can call itself more than once. The Fibonacci sequence — where each number is the sum of the previous two — needs two base cases (fib(0)=0, fib(1)=1) and two recursive calls. It's beautifully concise, but watch out: this naive version recomputes the same values over and over, so it becomes very slow for large n. That's a real lesson about recursion's cost.

#include <iostream>
using namespace std;

// Fibonacci: each number is the sum of the previous two.
// fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)
int fib(int n) {
    if (n < 2) return n;               // TWO base cases: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);    // TWO recursive calls
}

int main() {
    cout << "First 10 Fibonacci numbers:" << endl;
    for (int i = 0; i < 10; ++i) {
        cout << fib(i) << " ";         // 0 1 1 2 3 5 8 13 21 34
    }
    cout << endl;

    // NOTE: this naive version recomputes the same values many times,
    // so it gets slow fast. fib(40) makes over a billion calls!
    return 0;
}

// ✅ Expected output:
//    First 10 Fibonacci numbers:
//    0 1 1 2 3 5 8 13 21 34

4. Divide and Conquer: Fast Power

Recursion shines in divide-and-conquer, where each call shrinks the problem by half rather than by one. Fast exponentiation computes base^exp in O(log n) by squaring the result of power(base, exp/2). Halving the exponent each step means even 2^1000 takes only about ten calls — a huge improvement over multiplying one at a time.

#include <iostream>
using namespace std;

// Fast exponentiation by squaring: O(log n) instead of O(n).
// base^exp, where exp >= 0.
double power(double base, int exp) {
    if (exp == 0) return 1.0;          // BASE CASE: anything^0 = 1
    double half = power(base, exp / 2);// solve HALF the problem once
    if (exp % 2 == 0) return half * half;          // even exponent
    return half * half * base;                      // odd exponent
}

int main() {
    cout << "2^10 = " << power(2, 10) << endl;  // 2^10 = 1024
    cout << "3^4  = " << power(3, 4)  << endl;  // 3^4  = 81
    cout << "5^0  = " << power(5, 0)  << endl;  // 5^0  = 1
    return 0;
}

// ✅ Expected output:
//    2^10 = 1024
//    3^4  = 81
//    5^0  = 1

🔎 Deep Dive: the call stack & recursion vs iteration

Each function call pushes a stack frame holding its parameters and local variables. A recursive call pushes another frame before the current one finishes, so the frames pile up until the base case is reached — then they unwind, each returning its result to the caller below it:

factorial(3)            -> waits for factorial(2)
  factorial(2)          -> waits for factorial(1)
    factorial(1) = 1    <- base case returns
  factorial(2) = 2*1=2  <- unwinds
factorial(3) = 3*2 = 6  <- unwinds

Because the stack is finite, very deep recursion causes a stack overflow. Any recursion can be rewritten as a loop (sometimes with your own explicit stack). Choose recursion when it expresses the structure of the problem clearly — trees, graphs, divide-and-conquer — and a loop when the task is simple, deep, or performance-critical.

Pro Tips

• 💡 Write the base case first: it's the easiest part to forget, and forgetting it crashes the program.
• 💡 Make progress every call: each recursive call must move toward the base case (smaller n, narrower range).
• 💡 Trace small inputs by hand: walking through factorial(3) on paper builds real intuition.
• 💡 Watch for re-computation: naive Fibonacci is exponential; memoization or a loop fixes it.

🧠 Quick Recall

Predict the output before revealing the answer.

1. What does f(4) return?

int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}
cout << f(4);

10 — this sums 4 + 3 + 2 + 1 + 0 = 10.

2. What is wrong with this function?

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

No base case — it recurses forever (n keeps shrinking past 0), exhausting the stack and crashing with a stack overflow.

3. What does fib(5) return?

int fib(int n) {
    if (n < 2) return n;
    return fib(n-1) + fib(n-2);
}
cout << fib(5);

5 — the sequence is 0,1,1,2,3,5,... and fib(5) is the index-5 value, 5.

Common Errors (and the fix)

• No base case → stack overflow: the function calls itself forever. Always handle the smallest input directly with an early return.
• Not making progress: recursing with the same argument (e.g. f(n) instead of f(n-1)) never reaches the base case.
• Wrong base case value: factorial(0) must be 1, not 0 — an off-by-one base case poisons every result.
• Overflow of the result: factorial(21) exceeds even long long. Watch the value range, not just the recursion.
• Exponential blowup: naive Fibonacci recomputes subproblems; for big n use memoization or iteration.

📋 Quick Reference

Mini-Challenge: Recursive Palindrome

Check a word from both ends inward — a perfect fit for recursion. The outline gives you the base case and the recursive step.

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

// 🎯 MINI-CHALLENGE: Recursive palindrome check
// A string is a palindrome if it reads the same forwards and backwards.
// 1. Write bool isPalindrome(const string& s, int lo, int hi).
//    - BASE CASE: if lo >= hi, return true (met in the middle).
//    - If s[lo] != s[hi], return false.
//    - Otherwise recurse inward: isPalindrome(s, lo+1, hi-1).
// 2. Call it on a few words and print the results.
//
// ✅ Example output:
//    racecar -> 1
//    hello   -> 0
//    level   -> 1

int main() {
    // your code here
    return 0;
}

🎉 Lesson Complete

• ✅ Recursion is a function calling itself on a smaller subproblem
• ✅ Every recursive function needs a base case and a recursive case
• ✅ Each call must make progress toward the base case, or you get a stack overflow
• ✅ Functions can recurse zero, one, or many times (Fibonacci calls twice)
• ✅ Divide-and-conquer (halving) gives elegant O(log n) solutions like fast power

Practice quiz

Continue this course

• Previous: Functions
• Next: Lambda Expressions — Inline anonymous functions and captures
• Quick reference: C++ cheat sheet

Frequently asked questions

What is recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case that stops the recursion, and a recursive case that moves toward that base case.

What is a base case and why is it essential?

The base case is the simplest input the function can answer directly without recursing — for example factorial(0) is 1. Without a base case the function would call itself forever, exhausting the call stack and crashing with a stack overflow.

Is recursion slower than a loop?

Often slightly, because each call adds a stack frame and call overhead. Many recursive solutions can be rewritten as loops. Recursion is chosen when it expresses the problem far more clearly, such as tree traversal or divide-and-conquer algorithms.

What causes a stack overflow in recursion?

Recursing too deeply — either because the base case is never reached (infinite recursion) or because the depth is simply enormous. Each pending call uses stack memory, and the stack is finite, so eventually it runs out.

When should I prefer recursion over iteration?

Prefer recursion when the problem is naturally self-similar: traversing trees and graphs, divide-and-conquer (merge sort, quicksort), and generating combinations. For simple counting or summing, a loop is usually clearer and cheaper.

Related lessons

• conditionals