Recursion

Recursion solves a problem with a function that calls itself on a smaller problem of the same kind and combines the answers. It fits problems that contain copies of themselves, such as folders inside folders, or a formula defined through its own smaller values.

Explanation

You want to know how much space the folder /a takes on your computer. You add up the sizes of the files in it. But /a also holds the folders /a/b and /a/c, and everything in them counts too. So before you can finish /a, you need the size of /a/b, and before that, the sizes of the folders inside /a/b.

The size of a folder is the size of its own files plus the size of each folder inside it. A function size(folder) follows this rule. It starts with the folder's own files, calls itself on each folder inside, and adds what comes back. A folder with nothing inside asks nobody: its size is just its own files. This case, answered without calling further, is the base case.

Fig. 1 runs size("/a") on a small folder tree. Under the tree, the calls that have started and not finished yet form a row, the newest on the right.

Each folder shows the size of its own files. No call has started yet.

The call for /a starts with its own 2 MB and goes on the call stack.

The call for /a/b starts with its own 3 MB and goes on top of the call stack.

The call for /a/b/d starts with its own 5 MB. Nothing is inside, so this is the base case.

The call for /a/b/d returns 5 and leaves the stack. The call for /a/b goes on: 3 + 5 = 8.

The call for /a/b/e starts with its own 4 MB. Nothing is inside, so this is the base case.

The call for /a/b/e returns 4 and leaves the stack. The call for /a/b goes on: 8 + 4 = 12.

The call for /a/b returns 12 and leaves the stack. The call for /a goes on: 2 + 12 = 14.

The call for /a/c starts with its own 1 MB and goes on top of the call stack.

The call for /a/c/f starts with its own 6 MB. Nothing is inside, so this is the base case.

The call for /a/c/f returns 6 and leaves the stack. The call for /a/c goes on: 1 + 6 = 7.

The call for /a/c returns 7 and leaves the stack. The call for /a goes on: 14 + 7 = 21.

The call for /a returns 21: everything in /a takes 21 MB.

1/13

Fig. 1. The calls of size("/a"). A number beside a folder is its total so far; green means the folder is finished. The blue folder is the call that runs, the red lines lead to it from the calls that wait, and the boxes under the tree are the call stack.

size("/a") starts with 2 and calls size("/a/b"), which starts with 3 and calls size("/a/b/d"). Folder /a/b/d has nothing inside, so it answers 5 at once. The call for /a/b was waiting: it adds 5 to get 8 and goes on with the next folder in its list, /a/b/e, which answers 4. Now /a/b is finished with 12. The call for /a adds 12, does the same with /a/c (1 + 6 = 7), and finishes with 2 + 12 + 7 = 21 MB.

Nothing is skipped, because every waiting call remembers which folder it is about and how far it got in that folder's list. A finished call hands its answer to the one that called it, and that one goes on from where it stopped. On the way, the run also found the size of every folder inside /a.

Implementation

Calls and the call stack

Each size in Fig. 1 is a call of a function: one run of it, which returns to the line after the place it was called from. Every call has its own copy of the parameters and local variables.

The calls that have started and not yet finished are the call stack, the row of boxes in Fig. 1. It is a stack: a pile where the last item put on is the first taken off. A new call goes on top (the right end of the row), and when it returns, the call below it goes on.

A recursive function has these parts:

1. Base case: if the problem is small enough, answer directly, without calling (/a/b/d answers 5).

2. Smaller problem: call the same function on a smaller problem (/a/b asks about /a/b/d and /a/b/e).

3. Combine: build this call's answer from the answers that came back (/a/b adds 3 + 5 + 4 = 12).

4. Return: give the answer back to the call that asked (/a/b hands 12 to /a).

The program

The program reads n, the number of folders, and then for each folder i from 1 to n the size of its own files own[i] and the folder p it is in (0 for folder 1). For each folder we keep a list of the folders inside it, a vector children[p]. Reading "folder i is in folder p" adds i to children[p]. The folders in Fig. 1 are numbered /a = 1, /a/b = 2, /a/c = 3, /a/b/d = 4, /a/b/e = 5, /a/c/f = 6, so the input is:

6
2 0
3 1
1 1
5 2
4 2
6 3

The function size(v) starts its running total t with the folder's own files, then adds the answer for each folder inside. It stores the result in total[v], and the program prints the totals of all folders.

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

vector<long long> own, total;
vector<vector<int>> children;

long long size(int v) {
    long long t = own[v];
    for (int c : children[v]) {   // base case: a folder with nothing inside skips the loop
        t += size(c);             // smaller problem, combine
    }
    total[v] = t;
    return t;                     // return
}

int main() {
    int n;
    cin >> n;
    own.resize(n + 1);
    total.resize(n + 1);
    children.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> own[i] >> p;
        if (p != 0) children[p].push_back(i);
    }
    size(1);
    for (int i = 1; i <= n; i++) cout << total[i] << ' ';
    cout << '\n';
}

Team sizes

The same shape counts people in a company. Person 1 is the boss. People 2, 3 and 4 report to person 1, people 5 and 6 report to person 2, and person 7 reports to person 4. A person's team is that person plus the teams of everyone who reports to them.

Fig. 2. A person with nobody reporting to them has a team of 1. The other teams are for you to fill in.

The function starts like size, with the person themself counted as 1.

int team(int v) {
    int t = 1;  // the person v
    for (int c : reports[v]) {
        // combine: your line here
    }
    return t;
}

Factorial: one call per step

In factorial, each call makes only one call. The factorial is n! = 1 \cdot 2 \cdot \ldots \cdot n, and 0! = 1. Since n! = n \cdot (n-1)!, the function fact(n) asks fact(n - 1) and multiplies the answer by n. The base case is n == 0.

#include <iostream>
using namespace std;

long long fact(int n) {
    if (n == 0) return 1;         // base case
    long long rest = fact(n - 1); // smaller problem
    return n * rest;              // combine, return
}

int main() {
    int n;
    cin >> n;
    cout << fact(n) << '\n';
}

For n = 4 it prints 24. Each call has its own n, so when fact(3) gets 2 back, its n is still 3, although three calls with other values of n ran in between. The answer fits in long long up to n = 20; $21!$ is too large.

Fig. 3. The calls go to the right. The answers, under the calls, come back to the left: 1, 1, 2, 6, 24.

Depth and running time

fact(n) makes n + 1 calls with a fixed amount of work each, and size(1) makes one call per folder and goes over each list once, so both run in $O(n)$ time. The call stack takes memory in proportion to the deepest chain of waiting calls.

Counting calls also shows when a recursion repeats work. The Fibonacci numbers are F_0 = 0, F_1 = 1 and F_n = F_{n-1} + F_{n-2}:

long long fib(int n) {
    if (n < 2) return n;                // base case
    return fib(n - 1) + fib(n - 2);     // smaller problem, combine, return
}

Common mistakes

• A base case the input never reaches, such as if (n == 1) return 1; in fact when n = 0 is allowed, so the calls never stop. Make the base case cover the smallest allowed input (n == 0), and check that every call moves toward it.

• Thinking the call ends the function, when the outer call goes on from the line after the call with its own n. Put work that needs the smaller answer, or must come after it, below the call.

• One variable for all calls, such as a global running total t or loop counter i in size, which the inner calls overwrite. Declare the running total and the loop variable inside the function.

• Two calls that solve the same smaller problem again and again, as in fib, where each step up in n makes about 1.6 times as many calls. Store each answer the first time it is found and return it on the next call, which is memoization, the start of dynamic programming.

Similar techniques

When each call makes at most one call, as in factorial or the sum of digits, a loop does the same work without a deep call stack. When a call makes several calls, as with the folders, recursion is the simpler choice.

Depth-first search is recursion over a graph, a set of vertices joined by edges. A graph can lead back to a vertex already reached, so DFS marks the vertices it has visited. Folders can't lead back, so the folder walk needs no marks. It opens the folders in the same order as DFS would: 1, 2, 4, 5, 3, 6.

Backtracking is recursion that tries each choice in turn, goes deeper, and undoes the choice when the call returns. It lists all solutions, such as all orders of $n$ numbers.

Dynamic programming stores the answers to smaller problems, either with memoization or by filling a table in order without recursion.

Practice