Classic Recursive Algorithms: Factorial and Fibonacci

Recursion, at its heart, is about breaking down a complex problem into smaller, self-similar sub-problems. When we talk about classic recursive algorithms, we often point to two fundamental examples that perfectly illustrate this principle: the factorial function and the Fibonacci sequence. Understanding these will be your gateway to grasping more intricate recursive solutions.

Let's start with the factorial. The factorial of a non-negative integer 'n', denoted by 'n!', is the product of all positive integers less than or equal to 'n'. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. The key insight for recursion here is that we can define n! in terms of (n-1)!.

The recursive definition of factorial is:

• If n is 0, factorial(n) is 1 (this is our base case, the stopping condition).
• If n is greater than 0, factorial(n) is n * factorial(n-1) (this is our recursive step, calling itself with a smaller input).

Let's trace how factorial(4) would execute:

• factorial(4) calls factorial(3)
• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0)
• factorial(0) returns 1 (base case)
• factorial(1) receives 1, returns 1 * 1 = 1
• factorial(2) receives 1, returns 2 * 1 = 2
• factorial(3) receives 2, returns 3 * 2 = 6
• factorial(4) receives 6, returns 4 * 6 = 24

graph TD
    A[factorial(4)] --> B{n > 0?};
    B -- Yes --> C[4 * factorial(3)];
    C --> D[factorial(3)];
    D --> E{n > 0?};
    E -- Yes --> F[3 * factorial(2)];
    F --> G[factorial(2)];
    G --> H{n > 0?};
    H -- Yes --> I[2 * factorial(1)];
    I --> J[factorial(1)];
    J --> K{n > 0?};
    K -- Yes --> L[1 * factorial(0)];
    L --> M[factorial(0)];
    M --> N{n == 0?};
    N -- Yes --> O[1];
    L --> P[1 * 1 = 1];
    I --> Q[2 * 1 = 2];
    F --> R[3 * 2 = 6];
    C --> S[4 * 6 = 24];

Now, let's move on to the Fibonacci sequence. This sequence is defined by starting with 0 and 1, and each subsequent number is the sum of the two preceding ones. So, it looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The recursive definition is:

• If n is 0, fibonacci(n) is 0 (base case).
• If n is 1, fibonacci(n) is 1 (another base case).
• If n is greater than 1, fibonacci(n) is fibonacci(n-1) + fibonacci(n-2) (the recursive step).