Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 171 ยท Functions

Recursion

Learn recursion in C++ - base and recursive cases, how the call stack works, factorial, Fibonacci and fast power, stack overflow, tail calls, loops vs recursion and memoization.

A recursive function is one that calls itself. That sounds like a recipe for an endless loop, and done carelessly it is. Done well, recursion is one of the most elegant tools in programming: it lets you solve a problem by solving a smaller copy of the same problem and combining the answer. Folders contain folders, expressions contain expressions, a sorted list splits into two smaller sorted lists. Whenever the data has that shape, the recursive solution is often the shortest and clearest one.

In this lesson you'll learn the two parts every recursive function needs, watch the call stack grow and shrink, write classic examples (factorial, Fibonacci, fast power, walking a tree), see why deep recursion can crash a program and what tail calls do about it, and turn a painfully slow recursive function into a fast one with memoization. You should know Functions and Returning Values.

Base case and recursive case

Every correct recursive function has two kinds of paths:

  • A base case: an input small enough to answer directly, without recursing.
  • A recursive case: the function calls itself on a smaller input and uses the result.

"Smaller" is the key word. Each call must move closer to a base case, or the recursion never ends. The factorial n! = n ร— (n โˆ’ 1) ร— โ€ฆ ร— 1 is the textbook example, because it's defined in terms of itself: n! = n ร— (n โˆ’ 1)!, with 0! = 1.

C++ Factorial and a countdown

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

factorial(20) is 2,432,902,008,176,640,000, which is close to the limit of a 64-bit long long. factorial(21) would overflow, and since long long is signed, that's undefined behavior (see Integer Types). Recursion doesn't make numbers any bigger.

Notice the base case uses n <= 1, not n == 1. That makes factorial(0) correct, and it also means a negative argument stops right away instead of recursing forever. Making the base case catch "everything small" is a cheap way to be robust.

The call stack

Each time a function is called, the program reserves a stack frame on the call stack: space for its parameters, local variables and the address to return to. When the function returns, its frame is removed. With recursion, every call gets its own frame, so each level has its own copy of n. Nothing is shared or overwritten.

You can make the stack visible by indenting the output by depth:

C++ Watching the stack grow and shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The calls go "down" until the base case, then the results flow back "up". factorial(4) can't finish until factorial(3) returns, which waits for factorial(2), and so on. At the deepest point, four frames exist at once. That's the cost of recursion: memory proportional to the depth.

Stack overflow

The call stack is small. On Linux it's usually 8 MB for the main thread, on Windows 1 MB, and threads you create may get even less. Each frame costs anywhere from a few dozen bytes to kilobytes, depending on the locals. Recurse too deep and you run out, which is a stack overflow. In C++ there's no exception to catch: the operating system kills the process, usually with a segmentation fault.

This example crashes on purpose. It recurses with no realistic limit, and each level keeps a 1 KB buffer on the stack. Press Run to see what running out of stack looks like:

C++ A stack overflow (crashes on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The program never reaches its base case. It is killed in the middle of the recursion, and nothing after that point runs. Our sandbox allows an unusually large stack, so it gets about 300,000 levels deep (over 300 MB of stack) before the sandbox kills it. On a typical Linux machine with an 8 MB stack, the same program dies with a segmentation fault (SIGSEGV) after roughly 8,000 levels, and on Windows with a 1 MB stack after about 1,000. The std::fflush(stdout) call matters too: output still waiting in a buffer is lost when a process crashes.

Infinite recursion caused by a missing or unreachable base case ends the same way. GCC catches the obvious cases at compile time with the warning "infinite recursion detected" (-Winfinite-recursion, part of -Wall).

Habits that prevent stack overflows:

  • Make sure every path reaches a base case. Think about edge inputs: 0, negative numbers, empty containers.
  • Keep the depth small. Recursion that is logarithmic in the input (binary search, balanced trees, fast power, merge sort) is always safe; a million elements needs only about 20 levels. Recursion that is linear in the input (one level per element of a long list) is risky in C++.
  • Don't put large arrays in recursive functions. Use a std::vector, whose elements live on the heap.

Classic examples

Fast power: recursion that halves the problem

Computing x^n by multiplying n times takes n steps. Recursion gives a much faster approach: x^n = (x^(n/2))ยฒ, with one extra x when n is odd. Each call halves n, so even n = 1,000,000,000 needs only about 30 calls.

Walking a tree

Recursion shines on recursive data: a structure that contains smaller structures of the same kind. A folder holds files and other folders; a menu holds items and submenus. The code mirrors the data:

C++ Fast power and a folder tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

total_files has no explicit if for its base case. A folder with no subfolders simply skips the loop, and that is the base case. Many tree functions look like this.

power calls itself once per level and stores the result in half. Writing power(x, n / 2) * power(x, n / 2) instead would give the same answer but do the work twice at every level, throwing away the whole speedup. The next section shows how bad repeated work can get.

Fibonacci and the cost of repeated work

The Fibonacci sequence starts 0, 1, and each number after that is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, โ€ฆ The definition translates directly into code:

C++
long long fib(int n) {
    if (n < 2) { return n; }
    return fib(n - 1) + fib(n - 2);
}

It's correct and beautiful, and it's horribly slow. fib(5) calls fib(4) and fib(3), but fib(4) also calls fib(3). The same values are recomputed again and again, and the number of calls grows roughly 1.6 times with each step of n. fib(40) makes over 300 million calls.

The fix is memoization: remember each answer the first time you compute it, and look it up after that.

C++ Naive Fibonacci vs memoized

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The naive version needs 2,692,537 calls for fib(30); the memoized version needs 59. Memoization turns exponential time into linear time, at the cost of memory for the cache. It's the starting point of dynamic programming, a technique you'll use in Graphs, Recursion and Backtracking.

For a cache keyed by something other than a small integer, use a std::unordered_map (see std::unordered_map).

Tail calls

A call is a tail call when it's the very last thing a function does, with nothing left to compute afterward. return countdown(n - 1); is a tail call; return n * factorial(n - 1); is not, because the multiplication happens after the call returns.

Tail calls can be optimized: since the current frame isn't needed anymore, the compiler can reuse it instead of pushing a new one, effectively turning the recursion into a loop. You can often rewrite a function into tail form by passing the partial result along in an accumulator parameter:

C++
long long factorial_tail(int n, long long accumulator = 1) {
    if (n <= 1) {
        return accumulator;
    }
    return factorial_tail(n - 1, n * accumulator);   // tail call
}

But C++ does not guarantee tail-call optimization. GCC and Clang usually perform it at -O2, sometimes at -O1, and never at -O0, so a debug build can overflow the stack where the release build is fine. Objects with destructors in the frame can also block the optimization. (Clang offers a non-standard [[clang::musttail]] attribute to force it.) Never rely on tail calls to make deep recursion safe in portable C++; write a loop.

Recursion or a loop?

Anything recursion can do, a loop can do too, sometimes with an explicit stack (a std::vector used as a stack) to replace the call stack.

Prefer recursion when Prefer a loop when
The data is recursive (trees, nested structures, expressions) The problem is a simple sequence (sum, count, search a list)
The depth is small or logarithmic The depth could be large or depends on user input
The recursive version is much clearer (divide and conquer, backtracking) Performance is critical: loops have no call overhead

Here are both versions of the same depth-first walk. The loop keeps its own stack of work, so it can handle trees of any depth:

C++ The same tree walk with a loop and an explicit stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Both print the labels in the same order. The recursive version is shorter and obviously correct; the iterative one is immune to stack overflow because its stack lives on the heap. For most trees you'll meet, the recursive version is the right choice.

When you design a recursive function, trust the recursion. Assume the recursive call already works correctly for the smaller input (just as you trust std::sort), and only ask: "Given that answer, how do I build the answer for this input?" Then check that the base cases are right. Tracing every level by hand is useful for learning, but it's not how you reason about recursive code.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What happens when a recursive function's base case is never reached?

    Each call adds a stack frame. Without a reachable base case the stack eventually runs out, and the operating system kills the process. There is no standard exception for this.
  2. 2. int f(int n) { if (n <= 0) { return 0; } return n + f(n - 2); } What does f(5) return?

    f(5) = 5 + f(3) = 5 + 3 + f(1) = 5 + 3 + 1 + f(-1) = 9 + 0 = 9.
  3. 3. Why is the naive recursive Fibonacci so slow?

    fib(n - 1) and fib(n - 2) both recompute the same smaller values. Memoization stores each result once and brings the cost down to linear.
  4. 4. Which statement about tail calls in C++ is true?

    C++ doesn't guarantee tail-call optimization, so it may not happen in debug builds. In return n * f(n - 1) the multiplication happens after the call, so it isn't a tail call.

Summary

  • A recursive function needs a base case answered directly and a recursive case that moves toward it.
  • Each call gets its own stack frame; recursion uses memory proportional to its depth.
  • Too much depth causes a stack overflow, which crashes the program. Prefer recursion whose depth is small or logarithmic, and keep big objects off the stack.
  • Recursion fits recursive data and divide-and-conquer algorithms: trees, fast power, merge sort, backtracking.
  • Repeated work (naive Fibonacci) can make recursion exponentially slow; memoization caches results and fixes it.
  • Tail calls can be turned into loops by the optimizer, but C++ doesn't guarantee it. For deep or input-driven depth, write a loop, possibly with an explicit stack.

Next: Scope, Lifetime and Storage Duration, where you'll learn where variables are visible, how long they live, and what static really does.