Generate Fibonacci series up to n in DSA

The Fibonacci Series is one of the most common and fundamental concepts in Data Structures and Algorithms (DSA).
It forms the basis for understanding recursion, dynamic programming, and algorithm optimization.

🔢 What is the Fibonacci Series?

The Fibonacci series is a sequence of numbers where:

F(n) = F(n-1) + F(n-2)

with the first two numbers defined as:

F(0) = 0, F(1) = 1

So, the series looks like:

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

Each number is the sum of the two preceding numbers.

💡 Real-World Applications

You may be surprised, but the Fibonacci sequence appears in many real-world scenarios, such as:

🌻 Nature: Patterns in flowers and leaves
💰 Finance: Predicting stock market movements
🧬 Biology: DNA and population growth models
💻 Computer Science: Algorithm design and dynamic programming problems

🧠 Approach 1. Iterative Method

The iterative approach is more efficient and simple to implement.

✅ Algorithm Steps

Initialize first two numbers as 0 and 1.
Loop from 2 to n.
Calculate the next number as the sum of the previous two.
Print each number as you go.

💻 C Program Example

#include <stdio.h>

int main() {
    int n, first = 0, second = 1, next, i;

    printf("Enter the number of terms: ");
    scanf("%d", &n);

    printf("Fibonacci Series: ");
    for(i = 0; i < n; i++) {
        if(i <= 1)
            next = i;
        else {
            next = first + second;
            first = second;
            second = next;
        }
        printf("%d ", next);
    }

    return 0;
}

⏱ Time Complexity: O(n)
💾 Space Complexity: O(1)

🔁 Approach 2. Recursive Method

The recursive approach follows the direct mathematical definition of Fibonacci numbers.
However, it is less efficient because it performs repeated calculations.

💻 C Program Example

#include <stdio.h>

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

int main() {
    int n;
    printf("Enter the number of terms: ");
    scanf("%d", &n);

    printf("Fibonacci Series: ");
    for(int i = 0; i < n; i++) {
        printf("%d ", fibonacci(i));
    }

    return 0;
}

⏱ Time Complexity: O(2ⁿ)
💾 Space Complexity: O(n) due to recursion stack

⚙️ Optimized Approach (Using Dynamic Programming)

To improve performance, store results of previous calculations (called memoization).

💻 C Program Example

#include <stdio.h>

int fibonacci(int n, int memo[]) {
    if (memo[n] != -1)
        return memo[n];
    if (n <= 1)
        return n;

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

int main() {
    int n;
    printf("Enter the number of terms: ");
    scanf("%d", &n);

    int memo[n + 1];
    for(int i = 0; i <= n; i++)
        memo[i] = -1;

    printf("Fibonacci Series: ");
    for(int i = 0; i < n; i++)
        printf("%d ", fibonacci(i, memo));

    return 0;
}

⏱ Time Complexity: O(n)
💾 Space Complexity: O(n)

🎯 Comparison Table

🧩 Approach	⏱ Time Complexity	💾 Space Complexity	🚀 Efficiency
Iterative	O(n)	O(1)	✅ High
Recursive	O(2ⁿ)	O(n)	❌ Low
Dynamic Programming	O(n)	O(n)	⚡ Very High

🧩 Key Takeaways

Fibonacci series demonstrates recursion and iteration concepts clearly.
Iterative and dynamic programming methods are more efficient.
Always consider time complexity when implementing recursive solutions.

💬 Conclusion

The Fibonacci series is not just a simple number pattern—it’s a gateway to understanding recursion, optimization, and dynamic programming.

Whether you’re preparing for coding interviews or improving your DSA skills, mastering this concept gives you a solid foundation for solving more complex problems.