The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. It's a very famous sequence in mathematics and computer science.

The sequence typically starts from 0 and 1.

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

·         0 + 1 = 1

·         1 + 1 = 2

·         1 + 2 = 3

·         2 + 3 = 5

·         ...and so on.

Mathematical Definition:

·         F(n) = F(n-1) + F(n-2) (This is the general rule)

·         F(0) = 0 (This is Base Case 1)

·         F(1) = 1 (This is Base Case 2)

This problem, like Factorial, can be solved using both iteration and recursion.

This is the "bottom-up" approach and is the highly preferred method. It is fast, efficient, and uses very little memory.

Logic:

You only need to know the *last two* numbers to find the next one. We can use three variables:

·         a: The first number in the pair (e.g., 0)

·         b: The second number in the pair (e.g., 1)

·         next: The sum of a and b (e.g., 1)

Then, you "shift" the variables in a loop: a becomes b, b becomes next, and you calculate a new next.

Example Code: Iteration

/*

 * Example: Finding the first N Fibonacci numbers using a loop.

 * This is the efficient, "bottom-up" method.

 */

#include <stdio.h>

void print_fibonacci_loop(int n);

int main() {

    int count = 10;

    printf("First %d Fibonacci numbers (Iterative):\n", count);

    print_fibonacci_loop(count);

    return 0;

}

void print_fibonacci_loop(int n) {

    if (n <= 0) {

        return; // Nothing to print

    }

    // We need to use "long long" because the numbers get big.

    long long a = 0;

    long long b = 1;

    long long next;

    // Handle the first number (0)

    if (n >= 1) {

        printf("%lld ", a);

    }

    // Handle the second number (1) and all the rest

    for (int i = 2; i <= n; i++) {

        printf("%lld ", b);

        // Calculate the next number

        next = a + b;

        // "Shift" the variables for the next loop

        a = b;

        b = next;

    }

    printf("\n");

}

This method is fast and efficient. To find the 100th Fibonacci number, it only has to do ~100 additions. It uses a constant, small amount of memory (just a, b, next, and i).

This is the "top-down" approach. It's a perfect example of translating a mathematical definition directly into code. It is, however, extremely inefficient.

We take the mathematical definition and write it as a function:

1. The Recursive Step:

The general rule is F(n) = F(n-1) + F(n-2). This is a "double" recursion.

return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);

2. The Base Cases:

We need *two* "stop" conditions, or the recursion will never end.

Base Case 1: if (n == 0) { return 0; }

Base Case 2: if (n == 1) { return 1; }

Example Code: Recursion

/*

 * Example: Finding the N-th Fibonacci number using recursion.

 * This is the "elegant but very slow" method.

 */

#include <stdio.h>

long long fibonacci_recursive(int n);

int main() {

    int count = 10;

    printf("First %d Fibonacci numbers (Recursive):\n", count);

    // We have to call the function for each number

    for (int i = 0; i < count; i++) {

        printf("%lld ", fibonacci_recursive(i));

    }

    printf("\n");

    return 0;

}

long long fibonacci_recursive(int n) {

    // BASE CASE 1: F(0) = 0

    if (n == 0) {

        return 0;

    }

    // BASE CASE 2: F(1) = 1

    else if (n == 1) {

        return 1;

    }

    // RECURSIVE STEP: F(n) = F(n-1) + F(n-2)

    else {

        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);

    }

}

Warning: The recursive solution for Fibonacci is a classic example of "bad recursion." While it looks elegant, it is extremely slow. Trying to find fibonacci_recursive(50) could take minutes or even hours, while the loop version is instant.

The Problem: Redundant Calculations

Let's trace what happens when we call fib(5):

1.     fib(5) is called. It needs to calculate fib(4) and fib(3).

2.     To get fib(4), it calls fib(3) and fib(2).

3.     To get fib(3) (the *first* time), it calls fib(2) and fib(1).

4.     ...and so on.

Look at the full call tree. To solve fib(5):

·         fib(3) is calculated 2 times.

·         fib(2) is calculated 3 times.

·         fib(1) is calculated 5 times.

·         fib(0) is calculated 3 times.

This is horribly inefficient. We are calculating the exact same values over and over again. The loop version calculates each value only *once* and saves it.

This problem is called "exponential complexity" because the number of function calls (and the time it takes) doubles with each step. This is why the recursive version is a great *teaching* example but a terrible *practical* solution.

Conclusion: Recursion vs. Iteration for Fibonacci