Recursive patterns

Why this matters

Every pattern so far used loops. The same shapes can be printed by a function that calls itself, and writing them that way is the gentlest introduction to recursion. Recursion appears in interviews on trees, sorting and backtracking, and an interviewer often starts with a tiny exercise such as "print a triangle recursively" to see whether you can name the base case, the recursive call and the order of work. A pattern is a good place to learn this, because the output shows the order directly: if the rows come out upside down, the print is in the wrong place.

New words for this lesson

• Recursion: a function that calls itself.
• Base case: the simplest version of the problem, which needs no further call. It stops the recursion.
• Recursive call: the call that solves a smaller version of the same problem.
• Call stack: the pile of unfinished calls. Each call adds a frame holding its parameters and local variables. A returning call removes its frame.

A recursive triangle

A triangle of size n is a triangle of size n minus 1, followed by one more row of n stars. The smaller triangle is built the same way, down to size zero, and a triangle of size zero prints nothing. That sentence becomes code directly. If n is zero, return. Otherwise call the function with n minus 1, which prints every row above the last one, and then print the row of n stars.

Type 4 in the Input box and press Run.

The output for 4 is:

*
**
***
****

The row of stars is printed after triangle(n - 1) returns. So the smallest triangle prints first, at the top, and each larger call adds its row underneath. The row for n equal to 4 is printed last, at the bottom. Watch the call stack grow as the function goes down to zero, and watch the rows appear as it comes back up.

The program first calls triangle(4), which calls triangle(3), then triangle(2), then triangle(1), then triangle(0). The call triangle(0) returns at once. Then triangle(1) prints one star and returns. Then triangle(2) prints two stars and returns, and so on. The stars are printed on the way back up, which is why the smallest row comes first.

The stopping rule is if (n == 0) return;. Without it the calls would go on with n equal to minus 1, minus 2 and so on. Every recursive function needs a base case, and it must be reached after a finite number of calls. Here each call moves n one step closer to zero, so the base case is reached for any positive n.

A recursive inverted triangle

The inverted triangle is recursive too, and here the order of the work changes. The function prints its row of n stars first, and then calls itself with n minus 1. So the widest row prints first, at the top.

Type 4 in the Input box and press Run.

The output for 4 is:

****
***
**
*

Trace the first two calls. inverted(4) prints four stars and a line break, then calls inverted(3), which prints three stars and calls inverted(2). The calls continue until inverted(0), which returns at once and prints nothing.

The two programs use the same base case and the same call. Only the print moved. Put the print before the call and the rows come out largest first. Put it after the call and they come out smallest first. Many recursive algorithms do their work before the call, after it, or on both sides, and the position decides the result.

Counting down

The same function can print numbers, which shows the order of work without the picture. This program prints the numbers from n down to 1. The print comes before the call, so the largest number prints first.

Type 4 in the Input box and press Run.

4
3
2
1

count_down(4) prints 4 and calls count_down(3), which prints 3 and calls count_down(2), and so on. The call count_down(0) returns without printing. Each earlier call then finishes too, but it has nothing left to do, so the program ends after the 1.

A strong interview answer names the base case, says what the call does, and then says where the print goes and why. That short explanation shows the whole mechanism.

What happens inside a recursive call

Each call creates a new frame, a small block of memory that holds the function's parameters and local variables. A call to triangle(4) creates a frame with n equal to 4. That frame calls triangle(3), which creates a second frame with n equal to 3, and so on. The frames stack up, one on top of the other. The top frame is the one that runs now.

When a call returns, its frame is removed, and the frame below it continues from the line after its call. In the recursive triangle, the frame for triangle(3) waits while triangle(2) runs. When triangle(2) returns, triangle(3) resumes, prints its three stars and returns to triangle(4). That is why the rows appear in reverse order of the calls.

You can watch the order with a trace. This program prints a line when each call starts and when it ends.

enter 3
enter 2
enter 1
leave 1
leave 2
leave 3

The enter lines show the stack growing, and the leave lines show it shrinking in the opposite order.

What a missing base case does

The call stack has a limit. Each frame takes a little memory, and the total for the stack is fixed, commonly 8 MB on Linux. If a function keeps calling itself without reaching a base case, the stack fills up. Here is a program that does that on purpose.

#include <iostream>
 
int depth = 0;
 
void forever() {
    ++depth;
    forever();
}
 
int main() {
    forever();
}

Built with g++ -std=c++20 -O0 -Wall -Wextra, the compiler warns before you even run it:

main.cpp:5:6: warning: infinite recursion detected [-Winfinite-recursion]

When you run the program, the shell reports that the process was killed by the operating system. The exit status is 139, which is 128 plus signal number 11, a segmentation fault:

Segmentation fault (core dumped)

C++ has no StackOverflowError like Java. There is no exception to catch, because the stack is simply full, and the operating system stops the program. A sign of this in the real world is a crash with no message from your own code and, under a debugger, thousands of identical frames. The fix is a base case, and a check that every call moves the input toward it.

Compilers can sometimes turn a recursive call at the end of a function into a loop when you build with optimisation, such as -O2. Do not rely on that. Test recursion built with -O0, and treat the stack depth as a real limit.

Common mistakes

• No base case. The function calls itself until the stack is full, and the program crashes with a segmentation fault. Add if (n == 0) return; at the start.
• A call that moves the wrong way. If the triangle function calls triangle(n + 1), the value never reaches zero, and the result is the same crash even though the base case is correct. Read each call and ask whether its argument is closer to the base case than the current one.
• The print in the wrong place. Moving the print above the recursive call turns the triangle upside down. Decide where the work belongs before you write the call, and test with n equal to 2.
• A negative input. triangle(-1) never reaches n == 0, because n only gets smaller. Use if (n <= 0) return; when the input is not trusted.
• Using a function before it is declared. A recursive function can call itself, since its own name is known inside its body. A function that is called by main must still be written above main, or declared there with a prototype such as void triangle(int n);.

Debugging walkthrough: a recursive triangle prints upside down

Suppose you write the recursive triangle, but for an input of 3 the output is this:

***
**
*

You wanted the smallest row first. The widest row is at the top, which is the output of the inverted program. Walk through the steps.

Step 1: compare the first printed row with the first row you want. The first row has three stars, but a triangle must start with one.

Step 2: look at the order of the print and the recursive call. If the print comes before triangle(n - 1), the largest row prints first. That is the cause.

Step 3: move the print after the recursive call, so the call finishes first and the print runs on the way back up. The first row now has one star.

Step 4: check the base case. For n equal to 0 the function returns at once, so nothing is printed. Test n equal to 1 and n equal to 2 to confirm each stage.

The enter and leave trace from earlier works well here. It is the same idea as the call stack picture, written by hand, and it works for any recursive function.

Loops or recursion

A loop and a recursive function can print the same triangle. A recursive function uses memory for each call, so a deep recursion can fail even when its logic is right. For a triangle of 4 rows that is nothing, but at several tens of thousands of levels the stack can overflow. A loop has no such limit and is usually faster, so choose a loop when the depth is large and the shape is simple. Choose recursion when the problem is naturally made of smaller copies of itself, as with the trees and the backtracking problems later in the course.

Interview questions and real uses

Recursion appears in many interview questions, and these triangles are an early example. The interviewer may ask you to write a recursive function, to say what its base case is, and to say what the call stack looks like. A clear answer names the base case first, then the recursive call, then the work before or after the call.

What is the time complexity of the recursive triangle? Printing row k takes k steps, so the total is 1 + 2 + ... + n, which is about n squared over 2. That is O(n squared), the same as the loop version. The stack depth is n, so the extra space is O(n), where the loop version needs O(1).

How would you turn it into a loop? Replace the call by a for loop that counts from 1 up to n for the smallest-first order, or from n down to 1 for the largest-first order.

Recursive drawing appears in real software too. Fractal shapes, file-system trees and nested menus are all drawn by a function that draws a smaller copy of itself.

Practice

Try each exercise before you open its solution. Check it on paper with a small n before you run it.

1. Predict the output of the recursive triangle when the input is 3, and explain why the rows are printed in that order.

2. Write a function count_up(int n) that prints the numbers from 1 up to n, one per line. Put the print after the recursive call, and test it with the input 4.

void count_up(int n) {
    if (n == 0) {
        return;
    }
    count_up(n - 1);
    std::cout << n << '\n';
}

3. Predict the output of this function when it is called with 3: void twice(int n) { if (n == 0) return; std::cout << n << '\n'; twice(n - 1); std::cout << n << '\n'; }.

4. Find the bug. A program prints the recursive triangle, but the function has triangle(n + 1) as its recursive call. What happens, and why?

5. Write a recursive function that prints a row of n stars and then a line break, with no loop. Use the base case n == 0.

void stars(int n) {
    if (n == 0) {
        std::cout << '\n';
        return;
    }
    std::cout << '*';
    stars(n - 1);
}

6. Combine the two ideas. Write a recursive function that prints the shape with rows of 1, 2, 3, then 2, then 1 stars, for an input of 3. It is a small diamond made of recursion.

void rows(int k, int n) {
    for (int j = 0; j < k; ++j) std::cout << '*';
    std::cout << '\n';
    if (k < n) {
        rows(k + 1, n);
        for (int j = 0; j < k; ++j) std::cout << '*';
        std::cout << '\n';
    }
}

7. Explain why the function below never stops, then rewrite it so it stops when n reaches zero: void spin(int n) { std::cout << n << '\n'; spin(n); }.

What you now know

• A recursive function calls itself. It needs a base case that stops the calls, and each call must move closer to that case.
• The position of the print relative to the call decides the order of the rows: before the call prints the largest first, after the call prints the smallest first.
• Each call adds a frame to the call stack, and a returning call removes it, so the work after the call runs in the reverse order of the calls.
• In C++ a missing base case fills the stack and ends in a segmentation fault, not an exception. The compiler may warn with -Winfinite-recursion.
• A loop prints the same triangle with O(1) extra space. Use recursion when the problem is made of smaller copies of itself.