Lab: Recursive factorial and Fibonacci

Implement factorial and Fibonacci recursively and iteratively, compare performance, and explore the limits of each approach.

This lab asks you to implement both factorial and Fibonacci in two ways — recursive and iterative — and observe the tradeoffs firsthand.

Part 1: Recursive and iterative factorial

Write factorial.c containing two functions:

int factorial_recursive(int n);  /* recursive */
int factorial_iterative(int n);  /* using a for loop */

Both should compute n! and return the result. Test them for n = 0 through 12:

Expected output:

n=0  recursive=1        iterative=1
n=1  recursive=1        iterative=1
n=2  recursive=2        iterative=2
n=3  recursive=6        iterative=6
n=4  recursive=24       iterative=24
n=5  recursive=120      iterative=120
n=6  recursive=720      iterative=720
n=7  recursive=5040     iterative=5040
n=8  recursive=40320    iterative=40320
n=9  recursive=362880   iterative=362880
n=10 recursive=3628800  iterative=3628800
n=11 recursive=39916800 iterative=39916800
n=12 recursive=479001600 iterative=479001600

What happens with n=13? On a 32-bit int platform, 13! (6,227,020,800) overflows. Use long long and %lld to print it correctly.

Part 2: Recursive and iterative Fibonacci

Write fibonacci.c with:

long long fib_recursive(int n);  /* naive recursive */
long long fib_iterative(int n);  /* using a loop */

Print results for n = 0 through 20 and verify they match.

Now try timing: call fib_recursive(40) and fib_iterative(40). Can you feel the delay from the recursive version? On a modern machine, fib_recursive(45) takes several seconds.

Part 3: Memoised Fibonacci (extension)

Add a third version:

long long fib_memo(int n);

Use a static array to cache results:

long long fib_memo(int n) {
    static long long cache[100] = {0};
    if (n <= 1) { return n; }
    if (cache[n] != 0) { return cache[n]; }
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return cache[n];
}

Now fib_memo(90) is instant. This is the simplest form of dynamic programming — store solutions to subproblems so you never compute them twice.

Worked solution (Part 1)

#include <stdio.h>

long long factorial_recursive(int n) {
    if (n == 0) { return 1; }
    return n * factorial_recursive(n - 1);
}

long long factorial_iterative(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main(void) {
    for (int n = 0; n <= 12; n++) {
        printf("n=%-2d recursive=%-12lld iterative=%lld\n",
               n, factorial_recursive(n), factorial_iterative(n));
    }
    return 0;
}

What you practised

Writing recursive and iterative versions of the same function
Using long long to avoid overflow in factorial calculations
Observing the exponential cost of naive recursive Fibonacci
Implementing basic memoisation as a stepping stone to dynamic programming

The next module is Arrays and strings — how to store and process collections of values in C, including the zero-terminated char arrays that C uses for text.

Finished reading? Mark it complete to track your progress.