Recursion

Lesson 10 of 30 · Part 2 · Functions and arrays · about 15 minutes

A function can call other functions, and it can also call itself. This is recursion. When a problem has a smaller copy of the same problem inside it, recursion is a natural way to solve it. Counting down from 3, for example, is "say 3, then count down from 2":

1#include <stdio.h>2 3void countdown(int n) {4    if (n == 0) {5        printf("Go!\n");6        return;7    }8    printf("%d\n", n);9    countdown(n - 1);10}11 12int main(void) {13    countdown(3);14    return 0;15}

3
2
1
Go!

Every recursive function has two parts:

Each call makes n one smaller, so sooner or later it reaches 0 and the calls stop.

Factorial

The factorial of 5, written 5!, is 5 × 4 × 3 × 2 × 1 = 120. Look at it another way: 5! is 5 × 4!, 4! is 4 × 3!, and so on down to 1!, which is just 1. Write that sentence as code and you have a recursive function:

1#include <stdio.h>2 3int factorial(int n) {4    if (n <= 1) {5        return 1;6    }7    return n * factorial(n - 1);8}9 10int main(void) {11    printf("%d\n", factorial(4));12    printf("%d\n", factorial(5));13    return 0;14}

24
120

factorial(4) can't finish right away: it waits for factorial(3), which waits for factorial(2), which waits for factorial(1). Once factorial(1) returns 1, the waiting calls finish one by one, in reverse: 2 × 1, 3 × 2, 4 × 6.

Tip: Press Step on this one. Each call adds a stack frame in memory, on top of the one before, and each frame has its own n. The pile is tallest when n is 1. Then each return takes the top frame off and hands its value to the frame below.

Watching the calls pile up

To see the layers in the output too, give the function one more parameter, depth, that remembers how deep the call is, and indent by that much when printing:

1#include <stdio.h>2 3void indent(int depth) {4    for (int i = 0; i < depth; i++) {5        printf("    ");6    }7}8 9int factorial(int n, int depth) {10    indent(depth);11    printf("factorial(%d)\n", n);12    if (n <= 1) {13        indent(depth);14        printf("returns 1\n");15        return 1;16    }17    int result = n * factorial(n - 1, depth + 1);18    indent(depth);19    printf("returns %d\n", result);20    return result;21}22 23int main(void) {24    factorial(3, 0);25    return 0;26}

factorial(3)
    factorial(2)
        factorial(1)
        returns 1
    returns 2
returns 6

The indented lines are calls still waiting. The innermost call, factorial(1), returns first, then the outer ones return one by one. Unfinished calls are like a pile of plates: a new call goes on top, and return takes one off the top. That's why the part of memory holding these frames is called the stack.

Call first, print later

A recursive function can do things before the recursive call and after it. What comes before happens on the way in; what comes after waits until all the inner calls have returned:

1#include <stdio.h>2 3void show(int n) {4    if (n == 0) {5        return;6    }7    show(n - 1);8    printf("%d\n", n);9}10 11int main(void) {12    show(3);13    return 0;14}

The Fibonacci sequence

The Fibonacci sequence goes 0, 1, 1, 2, 3, 5, 8, 13... From the third number on, each one is the sum of the two before it. Number n is number n - 1 plus number n - 2. That's two smaller problems, so the function calls itself twice:

1#include <stdio.h>2 3int fib(int n) {4    if (n < 2) {5        return n;6    }7    return fib(n - 1) + fib(n - 2);8}9 10int main(void) {11    for (int i = 0; i <= 10; i++) {12        printf("%d ", fib(i));13    }14    printf("\n");15    return 0;16}

0 1 1 2 3 5 8 13 21 34 55 

It is short to write but slow to run. fib(5) works out fib(4) and fib(3), and fib(4) works out fib(3) all over again... The same numbers get computed again and again. Count the calls with a global variable (from the last lesson):

1#include <stdio.h>2 3int calls = 0;4 5int fib(int n) {6    calls++;7    if (n < 2) {8        return n;9    }10    return fib(n - 1) + fib(n - 2);11}12 13int main(void) {14    int a = fib(10);15    printf("fib(10) = %d, %d calls\n", a, calls);16    calls = 0;17    int b = fib(20);18    printf("fib(20) = %d, %d calls\n", b, calls);19    return 0;20}

fib(10) = 55, 177 calls
fib(20) = 6765, 21891 calls

Each time n goes up by 1, the number of calls grows about 1.6 times. fib(40) takes over 300 million calls.

Forgetting the base case

With no base case, or one that is never reached, the function keeps calling itself and the frames pile higher and higher. In a real program, the stack runs out of space and the program crashes (a "stack overflow"). Here nothing really crashes: the page stops at the line where it happened and tells you the stack ran out:

1#include <stdio.h>2 3int sum_to(int n) {4    return n + sum_to(n - 1);5}6 7int main(void) {8    printf("%d\n", sum_to(5));9    return 0;10}

stack overflow

sum_to forgot to stop when n is 0, so n keeps going down: 5, 4, 3... 0, -1, -2, never stopping. Press Step to watch the frames pile up one after another. Add if (n == 0) { return 0; } and it works.

Tip: When you write a recursive function, write the base case first, then the recursive step, and make sure every step gets closer to the base case.

Recursion or a loop?

What you can write with recursion you can often write with a loop too. Both functions below add up the digits of a number:

1#include <stdio.h>2 3int digit_sum(int n) {4    if (n < 10) {5        return n;6    }7    return n % 10 + digit_sum(n / 10);8}9 10int digit_sum_loop(int n) {11    int sum = 0;12    while (n > 0) {13        sum += n % 10;14        n /= 10;15    }16    return sum;17}18 19int main(void) {20    printf("%d %d\n", digit_sum(2048), digit_sum_loop(2048));21    return 0;22}

14 14

In C, simple counting and adding up is more direct with a loop, and faster too: no stack frame for every layer. When the problem itself is nested, layer inside layer (trees, or folders inside folders, which you'll meet later), recursion is much shorter and clearer.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

15
5050

1#include <stdio.h>2 3int sum_to(int n) {4 5}6 7int main(void) {8    printf("%d\n", sum_to(5));9    printf("%d\n", sum_to(100));10    return 0;11}

1024
81

1#include <stdio.h>2 3int power(int base, int exp) {4 5}6 7int main(void) {8    printf("%d\n", power(2, 10));9    printf("%d\n", power(3, 4));10    return 0;11}

4
1

1#include <stdio.h>2 3int count_digits(int n) {4    return 1 + count_digits(n / 10);5}6 7int main(void) {8    printf("%d\n", count_digits(2048));9    printf("%d\n", count_digits(7));10    return 0;11}

What you learned

• Recursion is a function calling itself. It needs a base case and a recursive step on a smaller problem.
• Each call has its own stack frame and its own variables; calls pile up, and each return takes one off.
• Statements after the recursive call run only once the inner calls have all returned.
• Recursion that calls itself twice, like Fibonacci, computes the same numbers many times over and is slow.
• With no base case, recursion never stops and the stack runs out.
• Use a loop for simple adding and counting; when the problem is nested layer inside layer, recursion is clearer.