Why Fibonacci Using Recursion in DSA C?

The Big Idea

What if a simple function could solve a complex sequence by calling itself again and again?

The Scenario

Imagine you want to find the 10th number in the Fibonacci sequence by writing down each number one by one on paper.

You start adding the last two numbers repeatedly to get the next one.

The Problem

Doing this by hand is slow and easy to make mistakes.

As the number gets bigger, you have to add many pairs again and again, which wastes time and causes confusion.

The Solution

Using recursion, the computer can break the problem into smaller parts automatically.

It calls the same function to find smaller Fibonacci numbers and combines them to get the answer.

This saves you from repeating the same work manually.

Before vs After

✗ Before

int fibonacci(int n) {
    int a = 0, b = 1, c, i;
    if (n == 0) return a;
    if (n == 1) return b;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

✓ After

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

What It Enables

Recursion lets you solve complex problems by breaking them into simpler, repeatable steps automatically.

Real Life Example

Calculating the number of ways to climb stairs when you can take one or two steps at a time uses the Fibonacci pattern.

Key Takeaways

Manual addition for Fibonacci is slow and error-prone.

Recursion breaks the problem into smaller calls, simplifying the process.

This method helps solve many problems that build on smaller subproblems.