Recursion

Solve a smaller version

A recursive function solves a problem by calling itself on a smaller version, and has a base case small enough to answer directly.

fact(4) = 4 × fact(3) = 4 × 3 × fact(2) … until fact(1), which just returns 1. Without the base case it never stops and the program crashes.

fact(3), call by call

#include <stdio.h>

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

int main() {
    printf("%d\n", fact(3));
    return 0;
}

1. Line 9: main asks for fact(3).
2. Line 5: n is 3, not the base case: it needs fact(2) first.
3. Line 5: fact(2) needs fact(1). Each call waits with its own n.
4. Line 4: fact(1) is the base case: returns 1.
5. Line 5: Back in fact(2): 2 × 1 = 2.
6. Line 5: Back in fact(3): 3 × 2 = 6.
7. Line 9: main prints 6.

Print on the way back

#include <stdio.h>

void count(int n) {
    if (n == 0) return;
    count(n - 1);
    printf("%d ", n);
}

int main() {
    count(3);
    printf("\n");
    return 0;
}

What does this print (spaces included)?

• 1 2 3
• 3 2 1
• 0 1 2 3

Exercise: Digit sum, recursively

Write a recursive int digitSum(int n): the sum of n's digits. No loops allowed. Read n (0 or more) and print the sum.

Exercise: Fibonacci

fib(0) = 0, fib(1) = 1, and fib(n) = fib(n−1) + fib(n−2). Write it recursively, read n (0 to 25) and print fib(n).