Ch6.11: Recursive Functions

Overview

A recursive function is a function that calls itself. Recursion is a natural way to express problems that can be broken down into smaller subproblems of the same form.

In this chapter, you will learn:

• what recursion is
• how to write a correct recursive function
• the importance of base cases
• how recursion uses the call stack
• why tail recursion is not guaranteed to be optimized in C++
• when recursion is appropriate and when iteration is better

1. What is recursion?

A recursive function solves a problem by solving a smaller version of the same problem. Every recursive function must have:

• a base case — when to stop
• a recursive case — how to reduce the problem

Without a base case, recursion never ends and the program eventually crashes due to stack exhaustion.

2. Example: factorial

The factorial function is defined mathematically as:

n! = n × (n - 1)!  
0! = 1
      

This definition is naturally recursive.

int factorial(int n)
{
    if(n < 0)
        ::fast_io::fast_terminate(); // factorial is undefined for negatives

    if(n == 0)
        return 1;                    // base case

    return n * factorial(n - 1);     // recursive case
}

Each call reduces the problem until it reaches the base case.

3. How recursion uses the call stack

Every function call creates a new stack frame containing:

• parameters
• local variables
• return address

Recursive functions create one stack frame per recursive call. For example:

factorial(4)
 ├─ factorial(3)
 │   ├─ factorial(2)
 │   │   ├─ factorial(1)
 │   │   │   └─ factorial(0)

When the base case returns, the stack unwinds in reverse order.

If recursion goes too deep, the program will crash due to stack overflow.

4. Tail recursion

A tail-recursive function is one where the recursive call is the last operation in the function.

int sum_tail(int n, int acc)
{
    if(n == 0)
        return acc;          // base case

    return sum_tail(n - 1, acc + n); // tail call
}

In some languages, tail recursion is optimized into a loop. However:

C++ does not guarantee tail-call optimization.

Compilers may optimize tail recursion, but you must not rely on it. If you need guaranteed constant stack usage, write an explicit loop instead.

5. When recursion is appropriate

Recursion is a good fit when:

• the problem is naturally recursive (trees, graphs, divide-and-conquer)
• the recursive structure matches the mathematical definition
• the depth is small and predictable

Recursion is a poor fit when:

• the depth may be large or unbounded
• stack usage is a concern
• iteration is simpler and clearer

6. More examples

6.1 Fibonacci (inefficient recursive version)

int fib(int n)
{
    if(n < 0)
        ::fast_io::fast_terminate();

    if(n <= 1)
        return n;

    return fib(n - 1) + fib(n - 2);
}

This version is extremely slow because it recomputes values repeatedly. Iterative or memoized versions are better.

Key takeaways

• A recursive function calls itself to solve smaller subproblems.
• Every recursive function needs a base case and a recursive case.
• Recursion uses the call stack; deep recursion risks stack overflow.
• C++ does not guarantee tail-call optimization.
• Use recursion when it matches the problem structure; use iteration when it is simpler or safer.