Bytebook Compiler

Functions

Recursion

Functions that call themselves: base cases, the call stack, and the factorial, Fibonacci, power, digit-sum and Tower of Hanoi programs.

5 min read4 runnable examples4-question quiz

A function is recursive when it calls itself. Recursion solves a problem by solving a smaller version of the same problem, until it reaches a case so small that the answer is obvious.

Every recursive function needs two parts:

  1. Base case — the smallest input, answered directly without recursion.
  2. Recursive case — express the answer using the same function on a smaller input.

Factorial

5! = 5 × 4! and 0! = 1. That definition is the code:

C
#include <stdio.h>

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

int main(void) {
    for (int i = 0; i <= 6; i++)
        printf("%d! = %lld\n", i, factorial(i));
    return 0;
}
Output
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
Try it Yourself

What happens on the call stack

Each call gets its own stack frame holding its own copy of n. Calls pile up until the base case, then return values flow back down:

main()factorial(4)factorial(3)factorial(2)factorial(1)topcall stack
While computing factorial(4), five frames are on the stack. factorial(1) returns 1, then each frame multiplies and returns.
Text
factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))
             = 24

Fibonacci

fib(0) = 0, fib(1) = 1, fib(n) = fib(n−1) + fib(n−2):

C
#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int i = 0; i < 12; i++) printf("%d ", fib(i));
    printf("\n");
    return 0;
}
Output
0 1 1 2 3 5 8 13 21 34 55 89
Try it Yourself

This is elegant but slow: fib(n) recomputes the same values again and again, making about 2ⁿ calls. You will fix this with memoisation in the Algorithms subject (Dynamic Programming).

f2f1f3f2f4f2f1f3f5
The call tree of fib(5). Highlighted calls are repeated work — fib(3) is computed twice and fib(2) three times.

More recursive classics

C
#include <stdio.h>

int sumDigits(int n)        { return n == 0 ? 0 : n % 10 + sumDigits(n / 10); }
long long power(int b, int e) {
    if (e == 0) return 1;
    long long half = power(b, e / 2);       // fast power: b^e = (b^(e/2))^2
    return e % 2 ? half * half * b : half * half;
}
void printBinary(int n)     { if (n > 1) printBinary(n / 2); printf("%d", n % 2); }
int gcd(int a, int b)       { return b == 0 ? a : gcd(b, a % b); }

int main(void) {
    printf("sumDigits(9045) = %d\n", sumDigits(9045));
    printf("power(3, 13) = %lld\n", power(3, 13));
    printf("13 in binary = "); printBinary(13); printf("\n");
    printf("gcd(84, 36) = %d\n", gcd(84, 36));
    return 0;
}
Output
sumDigits(9045) = 18
power(3, 13) = 1594323
13 in binary = 1101
gcd(84, 36) = 12
Try it Yourself

Tower of Hanoi

Move n disks from peg A to peg C using peg B, never placing a larger disk on a smaller one. The recursive insight: move n−1 disks out of the way, move the biggest disk, then move the n−1 disks back on top.

C
#include <stdio.h>

int moves = 0;

void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);
    printf("Move disk %d from %c to %c\n", n, from, to);
    moves++;
    hanoi(n - 1, via, from, to);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    printf("Total moves: %d\n", moves);   // always 2^n - 1
    return 0;
}
Output
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total moves: 7
Try it Yourself

Recursion vs iteration

Recursion Iteration (loops)
Code short, mirrors the maths sometimes longer
Memory one stack frame per call constant
Speed function-call overhead usually faster
Best for trees, divide and conquer, backtracking simple repetition

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What is the base case in int f(int n) { if (n == 0) return 0; return n + f(n - 1); }?

  2. 2

    What does f(4) return for the function in the previous question?

  3. 3

    What happens if a recursive function never reaches its base case?

  4. 4

    How many moves does Tower of Hanoi need for 4 disks?

Esc
↑↓ move↵ open