Recursion: base case and recursive case

A function that calls itself

• Recursion is when a function calls itself to solve a smaller version of the same problem.
• It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
• Without a base case, it would call itself forever and crash.

The base case

• The base case is the smallest problem you can answer directly, with no more calls.
• For factorial, 0! and 1! are both 1 — that is the base case.
• Always handle the base case first, so the recursion has somewhere to stop.

The recursive case

• The recursive case solves the problem using the answer to a smaller one.
• n! = n × (n - 1)!, so factorial(n) returns n * factorial(n - 1).
• Each call must move closer to the base case, or it will never stop.

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

int main(void) {
    printf("%d\n", factorial(5));  // 120
    return 0;
}

Recursion over an array

• You can recurse along an array by passing an index that moves forward each call.
• The base case is "the index has reached the end" (return 0 for a sum).
• The recursive case is a[i] + sum(a, i + 1, n) — this item plus the sum of the rest.

Common mistakes

• Recursion needs a base case, or the call stack overflows.
• Each call must move closer to the base case.

Now you try

• Write the base case first, then the recursive case that calls itself on a smaller input.
• Keep test values small so the numbers stay inside an int.
• Do not write a main — the checker provides one.