Fibonacci in C: solved exercise

Fibonacci in C: solved exercise

If you searched for a solved Fibonacci exercise in C, here are three implementations with complexity analysis: the classic recursive version (O(2^n)), the iterative version (O(n)), and the memoized recursive version (O(n)).

The Fibonacci sequence is the canonical example for understanding the difference between a naive recursive solution and a dynamic one: without a cache, the same subproblem is solved exponentially more times.

Problem statement

Implement three functions that return the n-th Fibonacci number (F(0)=0, F(1)=1):

  1. fib_recursive(n): recursive version without cache.
  2. fib_iterative(n): iterative version with O(1) space.
  3. fib_memo(n): recursive version with a memoization table.

Print the first 10 terms using each version.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <stdio.h>
#include <string.h>

#define MAX 64

/* Recursive: O(2^n) time */
long long fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

/* Iterative: O(n) time, O(1) space */
long long fib_iterative(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

/* Memoization */
static long long memo[MAX];

long long fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main(void) {
    memset(memo, 0, sizeof(memo));

    printf("Recursive: ");
    for (int i = 0; i < 10; i++) printf("%lld ", fib_recursive(i));

    printf("\nIterative: ");
    for (int i = 0; i < 10; i++) printf("%lld ", fib_iterative(i));

    printf("\nMemo:      ");
    for (int i = 0; i < 10; i++) printf("%lld ", fib_memo(i));

    printf("\n");
    return 0;
}

Expected output

1
2
3

Recursive: 0 1 1 2 3 5 8 13 21 34 
Iterative: 0 1 1 2 3 5 8 13 21 34 
Memo:      0 1 1 2 3 5 8 13 21 34

Common mistakes

  • Not defining the base case: without if (n <= 1) return n the recursion is infinite and causes a stack overflow.
  • Using int for large n: F(47) exceeds the range of int (2,147,483,647); use long long to safely reach F(92).
  • Forgetting to zero-initialize the memo table: static gives zero-initialized memory, but a stack-allocated array requires an explicit memset.
  • Benchmarking the recursive version for n > 40: the runtime grows exponentially and can freeze the program for several seconds.

Practical use

Fibonacci appears in the analysis of divide-and-conquer algorithms, in computing the worst-case complexity of quicksort, and in data structures like Fibonacci heaps. Memoization is the first step toward dynamic programming.

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Why is the recursive version so slow for large values?

Because it recomputes the same subproblems multiple times. To compute F(5), it calls F(3) twice and F(2) three times. The complexity is O(2^n): for F(40), over one billion recursive calls are made.

When should I use the iterative version versus the memoized version?

Use the iterative version when you only need the n-th term: it uses O(1) space. The memoized version is useful when you need multiple terms at different times (separate calls), since it reuses the cache across them.

Is there a direct formula to compute F(n)?

Yes: Binet’s formula, F(n) = (φ^n − ψ^n) / √5 where φ = (1+√5)/2. However, it uses double and accumulates rounding errors for n > 70, so in C the iterative version with 64-bit integers is preferred.