To add 0 to 4, add 0 to 3 and then add 4. A function can work that way by calling itself. Watch the cards pile up.
A function that calls itself
factorial(5) calls factorial(4), and on down to factorial(0)
#include <stdio.h> int sum_to(int n){ if (n == 0) return 0; int rest = sum_to(n - 1); return n + rest;} int factorial(int n){ if (n == 0) return 1; int rest = factorial(n - 1); return n * rest;} int main(void){ int s = sum_to(4); printf("sum_to(4) = %d\n", s); int f = factorial(5); printf("factorial(5) = %d\n", f); return 0;}main calls sum_to(4).
- frames on the stack
- 1
Output
Describe this picture
The 26 lines of recursion.c with the line about to run marked, beside a picture of the call stack. Under the label “Call stack” is one card per call that has not returned yet, main’s at the top and each new call’s card under the card of the call that made it. A card names its call on the left, such as factorial(3), and shows that call’s own variables as small boxes, a name over a value: main’s s and f, and each call’s n and rest. A value not written yet shows as ”?”. The running call’s card is edged in the accent colour, and the box the last line wrote is outlined. When a call reaches its return, a badge on the right of its card shows what it works out, such as “5 × 24 = 120”, then the value it hands back, ”→ 120”; as the card fades, that value flies into the box of the card above that receives it. The clip plays the program once, about 28 seconds, and rests on the end. First sum_to(4) plays quickly: five cards, n = 4 down to 0, then the sums 1, 3, 6 and 10 on the way back, and 10 lands in s. Then factorial(5) plays slowly: six cards, n = 5 down to 0, each with rest ”?”, so with main there are seven cards. factorial(0) returns 1, and the cards fold back one at a time, 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24 and 5 × 24 = 120, which lands in f. Under the picture are one sentence on the current step, the readout “frames on the stack”, which counts the cards with main’s, and the output once the program prints. The transport plays and pauses, steps one line back or forward, and scrubs; a paused step is kept in the page address as recursion.step.
Each call has its own n
Here is sum_to, the first function in the program:
int sum_to(int n)
{
if (n == 0)
return 0;
int rest = sum_to(n - 1);
return n + rest;
}It has two cases. When n is 0 the answer is 0, with no more work: that is the base case. Any other n is the recursive case: sum_to asks for sum_to(n - 1), the sum of everything below n, and adds n to it.
main calls sum_to(4). That call cannot finish until it knows sum_to(3), so it calls it, and sum_to(3) calls sum_to(2), and so on down to sum_to(0), which answers 0 at once. Watch the cards in the first seconds of the clip. Each call gets a new card, its own frame, with its own n, as The call stack (1.3) showed for any function call. There are five boxes called n on the screen at once, holding 4, 3, 2, 1 and 0. The calls do not share one n.
A card that has made its call is not finished, and it has not forgotten what it was doing. It waits on line 7 with rest still ”?”, until the card under it returns. Then its work resumes from that line: rest gets the value, and the card works out its sum. On the way back the sums are 0 + 1 = 1, 1 + 2 = 3, 3 + 3 = 6 and 6 + 4 = 10. So sum_to(4) is 10, and the answer is built on the way back, not on the way down.
factorial has the same shape, with × in place of + and 1 as the answer for 0. Now the clip slows down. Six cards pile up, from factorial(5) down to factorial(0); with main’s that makes seven frames. That is the deepest point, and each waiting card is a multiplication half done: 5 × ?, 4 × ?, and so on. Then factorial(0) returns 1. That 1 is not the answer. It travels back up the cards and is multiplied five times: 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24 and 5 × 24 = 120.
Key idea
A recursive function has a base case, which answers without calling, and a recursive case, which calls itself on a smaller input and uses the answer. Every call has its own frame, and the frames wait until the calls above them return.
The code and its cost
The shape of a recursive function
Every recursive function on this course has the same two parts:
if (the input is as small as it gets)
return the answer directly; /* base case */
answer = the same function on a smaller input; /* recursive case */
return what this call adds to that answer;The recursive case must make the input smaller, and every chain of smaller inputs must reach a base case. sum_to and factorial take 1 off n, so from any n of 0 or more they reach 0 after n calls.
The program stores the result of each call in its own variable, rest, on its own line, before using it. That is a choice for this course: it gives the picture one clear moment when the value comes back. return n + sum_to(n - 1); does the same work.
Counting the calls and the frames
sum_to(4) made 5 calls: n = 4, 3, 2, 1 and 0. In general, write T(n) for the calls that sum_to(n) makes. sum_to(0) makes one call, itself, and any other sum_to(n) makes one call plus those of sum_to(n − 1):
T(0) = 1, T(n) = T(n − 1) + 1, so T(n) = n + 1.
The deepest point is when all those calls are waiting at once, so the stack holds n + 1 frames of sum_to on top of main’s. For factorial(5) that is 6 frames, 7 with main’s, as the readout under the picture says at the deepest step. Time grows with n, and so does the memory: one frame per call still waiting.
A loop does the same sum in one frame:
int sum_loop(int n)
{
int total = 0;
for (int i = 1; i <= n; i++)
total = total + i;
return total;
}Two ways it fails
No base case. Here is a function that forgets it:
int bad(int n)
{
return n * bad(n - 1);
}bad(5) calls bad(4), which calls bad(3), and on past 0 into negative numbers; no call ever returns. gcc sees it and warns:
no-base-case.c:3:5: warning: infinite recursion detected [-Winfinite-recursion]Built with the address sanitiser and run, the program stops with ERROR: AddressSanitizer: stack-overflow. Each call took another frame until the stack had no room left.
Too deep. A correct function fails the same way if the chain of calls is too long. The stack here is 8 MiB, and each call of sum_to takes 48 bytes of it in a plain build: 32 for its n, its rest and some padding, 8 for the saved frame pointer (rbp), and 8 for the return address. 8,388,608 bytes ÷ 48 is about 174,763 frames. I measured it on my machine with a twin of sum_to (the same frame, but it returns n, so the answer cannot overflow): the program crashed for n of about 174,600 and up, the exact n moving a little from run to run, because a little of the stack is already in use when main starts. So the plain build of sum_to dies for n around 175,000.
Running it yourself
The code pane shows the whole program. Build and run it with:
gcc -std=c11 -Wall -Wextra -pedantic recursion.c -o recursion
./recursionIt prints sum_to(4) = 10, then factorial(5) = 120.
Worked example
sum_to(4) by hand. Write each call as what it adds to the call below it:
sum_to(4) = 4 + sum_to(3) = 4 + 3 + sum_to(2) = 4 + 3 + 2 + sum_to(1) = 4 + 3 + 2 + 1 + sum_to(0) = 4 + 3 + 2 + 1 + 0 = 10.
That is five calls, sum_to(4) to sum_to(0). Before you read on: what does factorial(3) hand back to factorial(4)? (6: it is 3 × 2 × 1 × 1. Step the clip to the card factorial(3) returning, and its badge shows 3 × 2 = 6.)
How far factorial can go. The largest int here is 2,147,483,647. factorial(12) is 479,001,600, which fits. factorial(13) would be 13 × 479,001,600 = 6,227,020,800, which does not: the multiplication overflows, and signed overflow makes the behaviour of the whole program undefined, not just the result. So int factorial(int n) is right only up to n = 12, long before the stack is any trouble.
How far sum_to can go. The same limit stops sum_to first, too. sum_to(n) is n(n + 1)/2. For n = 65,535 that is 2,147,450,880, which fits; for n = 65,536 it is 2,147,516,416, which does not. So the answer overflows at n = 65,536, while the stack would last until about 175,000.
The two failures side by side.
| Function | What happens | When |
|---|---|---|
bad(5), no base case | every call calls again; the stack overflows | always, whatever n is |
sum_to(n), correct | n + 1 frames at the deepest point | stack overflow from n of about 175,000 here |
sum_loop(n), a loop | one frame | never overflows the stack |
Where it’s used
Trees and folders. A folder holds files and other folders, and a tree node holds other trees. A function that lists a folder calls itself on each folder inside it, and its base case is a folder with no folders in it. Tree traversals (12.3) work this way.
The FFT. The fast Fourier transform splits a signal of n samples into two halves of n/2, transforms each half by calling itself, and combines the two answers; see FFT algorithms.
Parsers. A bracket may hold an expression that holds another bracket. A parser for such text calls itself at each opening bracket and returns at the matching closing one.
Sorting. Merge sort (17.5) and quicksort (17.6) split an array into parts, sort each part by calling themselves, and put the parts together.
Reference card
| Idea | In this lesson |
|---|---|
| base case | answers without calling: if (n == 0) return 0; |
| recursive case | calls itself on a smaller input, then uses the answer |
| one frame per call | every call has its own n and rest |
| the answer is built | on the way back, as each call returns |
| calls of sum_to(n) | T(n) = T(n − 1) + 1, T(0) = 1, so n + 1 |
| deepest stack | n + 1 frames of sum_to, plus main’s |
| no base case | never stops; gcc warns, the stack overflows |
| too deep | stack overflow; about 175,000 frames of 48 bytes in 8 MiB here |
| the same with a loop | one frame |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, a stack of 8 MiB. The cards in the picture show names and values only; the frame sizes are the real ones from a plain build.