Recursive Functions in C: Factorial and Fibonacci, Revisited with Recursion Trees

by

Recursion — a function calling itself — was already introduced with full examples in Part 2 of the Functions series. This post revisits the two examples the syllabus specifically calls out, factorial and Fibonacci, with an added visual tool that makes recursion easier to reason about: the recursion tree. This is the final post of the Unit III series — Post 3 mapped the rest of the functions syllabus to the existing series.

Quick Recap: The Two Rules of Recursion

Every correct recursive function needs: 1) A BASE CASE — a condition simple enough to answer directly, without recursing further. 2) A RECURSIVE CASE that moves toward the base case with each call. Miss either one, and the function either never recurses at all, or recurses forever until the program crashes with a stack overflow.

Factorial: A Linear Recursion Tree

#include <stdio.h>

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

int main() {
    printf("5! = %d\n", factorial(5));
    return 0;
}

Sample Output

5! = 120

Factorial’s recursion tree is a simple straight line — each call makes exactly one further recursive call:

factorial(5)
  └── factorial(4)
        └── factorial(3)
              └── factorial(2)
                    └── factorial(1) --> returns 1 (base case)
                  <-- 2 * 1 = 2
            <-- 3 * 2 = 6
      <-- 4 * 6 = 24
<-- 5 * 24 = 120

Because each level only branches into one further call, factorial makes exactly n calls total (for factorial(n)) — its running time is O(n), directly proportional to n.

Fibonacci: A Branching Recursion Tree

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("fibonacci(5) = %d\n", fibonacci(5));
    return 0;
}

Sample Output

fibonacci(5) = 5

Unlike factorial, each Fibonacci call branches into two further calls. The recursion tree for fibonacci(5):

                          fib(5)
                        /        \
                   fib(4)          fib(3)
                  /      \        /      \
             fib(3)      fib(2) fib(2)   fib(1)
            /     \      /   \   /   \
       fib(2)  fib(1) fib(1) fib(0) fib(1) fib(0)
       /    \
   fib(1)  fib(0)
Notice the repeated work: fib(3) is computed TWICE, fib(2) is computed THREE times, in this small tree — and the redundancy gets exponentially worse as n grows. This naive version of Fibonacci has time complexity O(2ⁿ), which becomes impractically slow for anything beyond roughly n = 40, even though the PROBLEM itself has a perfectly fast O(n) iterative solution.

The Efficient Alternative: Iterative Fibonacci

#include <stdio.h>

int fibonacciIterative(int n) {
    int a = 0, b = 1;

    if (n == 0) return a;

    for (int i = 2; i <= n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }

    return b;
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("%d ", fibonacciIterative(i));
    }
    printf("\n");
    return 0;
}

Sample Output

0 1 1 2 3 5 8 13 21 34
The real lesson here: Recursion is a natural FIT for problems that are defined in terms of smaller versions of themselves (which Fibonacci's mathematical definition literally is), and it often produces the shortest, clearest code. But "clearest to write" and "fastest to run" are different goals — always check whether a recursive solution is repeating identical work (as the tree above visibly shows), and prefer an iterative or memoized version when it is.

Recursion vs. Iteration: The Trade-off, Revisited

  Factorial Fibonacci (naive recursive)
Recursion tree shape Linear (single branch) Exponential branching
Time complexity O(n) O(2ⁿ)
Repeated subproblems? No Yes, heavily

Summary

  • Every recursive function needs a base case and a recursive case that progresses toward it.
  • A recursion tree visualizes every call a recursive function makes — a straight line for factorial, an exponentially branching tree for naive Fibonacci.
  • Branching recursion (like Fibonacci) can recompute the same subproblem many times over — a strong signal to consider an iterative or memoized alternative for real use, even though the recursive version is often the clearest to read and write.

This wraps up Unit III: Searching, Sorting, Functions, and Recursion — and with it, the first three units of the syllabus series. Units IV (Structures, Unions, Pointers) and V (Data Structures: Stacks, Queues, Linked Lists, Trees/Graphs) are planned next.

Further Reading

Leave a Comment