Home / C++ / Recursion and the function call stack

C++ PROGRAMMING · 16 MIN STUDY

Recursion and the function call stack

Solve a problem by reducing it to a smaller version, with a correct base case and progress toward it.

Learning objectives

  • Define recursion and identify a base case.
  • Trace recursive calls and returns.
  • Explain how the call stack stores active function calls.
  • Recognize infinite recursion and stack-depth risks.

Prerequisites: functions, parameters, return values, and conditional statements. Review Functions and Making choices with if and switch first.

What is recursion?

Recursion happens when a function calls itself, directly or indirectly, to solve a smaller version of the same problem. A correct recursive solution needs two parts: a base case that stops calling, and a recursive step that makes progress toward that base case.

Example: countdown

C++17
#include <iostream>
#include <stdexcept>

void countdown(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be non-negative");
    }
    if (n == 0) {          // base case
        std::cout << "Go!\n";
        return;
    }
    std::cout << n << '\n';
    countdown(n - 1);      // smaller problem
}

int main() {
    countdown(3);
}
3 2 1 Go!

Trace the calls

countdown(3)
  prints 3, calls countdown(2)
    prints 2, calls countdown(1)
      prints 1, calls countdown(0)
        base case prints Go! and returns
      countdown(1) finishes
    countdown(2) finishes
  countdown(3) finishes

Each active call has its own parameter value. The runtime call stack tracks these unfinished calls. When the base case returns, control resumes in the previous call, then the previous one, until the first call finishes.

Example: factorial

For a positive integer n, factorial is the product of all positive integers up to n. Its mathematical definition is 0! = 1 and n! = n × (n - 1)! for positive n.

C++17
#include <limits>
#include <stdexcept>

long long factorial(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be non-negative");
    }
    if (n == 0) {
        return 1;
    }

    const long long previous = factorial(n - 1);
    if (previous > std::numeric_limits<long long>::max() / n) {
        throw std::overflow_error("factorial does not fit in long long");
    }
    return n * previous;
}

This function needs <limits> for the maximum representable long long value and <stdexcept> for its exceptions. Signed integer overflow in C++ is undefined behavior; it is not a guaranteed wraparound. The check runs before multiplication and throws std::overflow_error when the result cannot fit. On common 64-bit implementations, 20! fits in long long but 21! does not. The function is still recursive, so very large inputs can exhaust the call stack even before arithmetic becomes the limiting factor.

How to design a recursive function

  1. Describe the problem in one sentence.
  2. Find the smallest input that can be answered directly. That is the base case.
  3. Write the recursive call using a smaller input.
  4. Prove that each call moves closer to the base case.
  5. Trace a small input by hand before running it.

Recursion versus iteration

Many recursive tasks can also be solved with loops. A loop often uses constant extra call-stack space, while a recursive solution typically uses one stack frame per active call. Recursion can make tree traversal and divide-and-conquer algorithms easier to express, but very deep recursion can exhaust the call stack. Choose based on clarity, input depth, and resource limits.

Time and space complexity

For countdown(n) and the recursive factorial(n), each call performs constant work and makes one call with a value one smaller. For non-negative n, both therefore take O(n) time and use O(n) call-stack space. The recursive sum_to_n(n) practice solution has the same bounds. A loop-based countdown uses O(1) extra space. These bounds describe growth with input size; they do not guarantee that an arbitrarily deep recursive call will fit the program's available stack.

Common mistakes

  • Missing a base case.
  • Writing a recursive step that does not move toward the base case.
  • Forgetting to return the recursive result.
  • Assuming recursion is always faster or more memory-efficient than a loop.
  • Ignoring integer overflow in numeric examples.

Practice

  1. Change countdown to start at 5. Draw every call before running it.
  2. Write a recursive function that sums integers from 1 through n, with a base case for zero.
  3. Explain why sum(n - 1) progresses toward the base case but sum(n + 1) does not.
  4. Rewrite countdown using a loop and compare the two traces.

Practice solutions

Show worked solutions
  1. Call countdown(5). The calls are countdown(5), (4), (3), (2), (1), then (0); the base case prints Go!.
  2. For non-negative, reasonably small n: 
    long long sum_to_n(int n) {
    if (n == 0) return 0;
    return n + sum_to_n(n - 1);
}
    Each call reduces n by one until zero. The result type has a finite range, so use only inputs whose sum fits.
  3. n - 1 gets closer to zero for positive n. n + 1 moves away from zero, so it never reaches the base case n == 0.
  4. for (int n = 5; n > 0; --n) {
    std::cout << n << '\n';
}
std::cout << "Go!\n";
    The loop produces the same visible sequence without recursive calls.

Check your understanding

What are the two required parts of a basic recursive design?

Answer: A base case and a recursive step that makes progress toward it. Without the base case, calls may continue until the program exhausts resources.

Summary

Recursion solves a problem through smaller calls. The base case stops the process, the recursive step makes progress, and the call stack remembers unfinished work. Always trace small inputs and consider maximum depth.

References