C Program To Display Fibonacci Sequence

The Fibonacci sequence in C teaches you loops, recursion, and efficiency. First, let us help you understand what a Fibonacci Series in C is and how it is formed! 

What is the Fibonacci Sequence?

It’s a sequence of numbers. Each number is the sum of the two that came before it. It starts with 0 and 1.

So, it goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5

And so on.

The rule is F(n) = F(n-1) + F(n-2). Simple. Now let’s code it in C Programming.

Method 1: Using a for Loop (The Iterative Approach)

This is the most straightforward way. You initialize the first two numbers, then loop to calculate the rest.

Code:

#include <stdio.h>

void printFibonacci(int n) {
    int t1 = 0, t2 = 1;
    int nextTerm;

    printf("Fibonacci Series: ");

    for (int i = 1; i <= n; ++i) {
        printf("%d, ", t1);
        nextTerm = t1 + t2;
        t1 = t2;
        t2 = nextTerm;
    }
    printf("\n");
}

int main() {
    int terms;
    printf("Enter the number of terms: ");
    scanf("%d", &terms);
    
    printFibonacci(terms);
    
    return 0;
}

Explanation:

1. We start with t1 = 0 and t2 = 1.
2. The for loop runs n times, for the number of terms you want.
3. Inside the loop, we first print the current t1.
4. Then, we calculate the nextTerm by adding t1 and t2.
5. To prepare for the next iteration, we update t1 to be the old t2, and t2 becomes the new nextTerm. This slides our window forward.
6. This is efficient. The complexity is O(n) because it does a constant amount of work n times.

Method 2: Using Recursion

Recursion is when a function calls itself. For Fibonacci, it’s a natural fit for the mathematical definition, but it has a major flaw.

Code:

#include <stdio.h>

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

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

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

    return 0;
}

Explanation:

1. The fib function has a “base case”: if n is 0 or 1, it just returns n. This is the stop condition for the recursion.
2. If n is greater than 1, the function calls itself for n-1 and n-2 and returns their sum.

Why Recursion is Bad Here:

This approach is very inefficient. To calculate fib(5), it calculates fib(4) and fib(3). But to get fib(4), it has to calculate fib(3) and fib(2). Notice fib(3) is calculated twice. This redundancy grows exponentially. The time complexity is O(2^n), which is terrible for anything but small numbers. It’s a classic example of how not to use recursion in production code, but a great one for understanding how recursion works.

Method 3: Using an Array (Memoization)

We can fix the recursive solution’s inefficiency by storing the results we’ve already calculated. This is a form of dynamic programming called memoization.

Code:

#include <stdio.h>

long long fib_array[100]; // Array to store fibonacci numbers

long long fib(int n) {
    if (n <= 1) {
        return n;
    }
    
    // Check if we have already computed it
    if (fib_array[n] != 0) {
        return fib_array[n];
    }
    
    // If not, compute and store it
    fib_array[n] = fib(n - 1) + fib(n - 2);
    return fib_array[n];
}

int main() {
    int terms;
    printf("Enter the number of terms (up to 92): ");
    scanf("%d", &terms);
    
    // Initialize array with 0s
    for(int i = 0; i < 100; i++) {
        fib_array[i] = 0;
    }

    printf("Fibonacci Series: ");
    for (int i = 0; i < terms; i++) {
        printf("%lld, ", fib(i));
    }
    printf("\n");
    
    return 0;
}

Explanation:

1. We have a global array fib_array to store computed values.
2. Before computing fib(n), we check if fib_array[n] is already non-zero.
3. If it is, we return the stored value instantly.
4. If not, we compute it recursively, but crucially, we store the result in fib_array[n] before returning.
5. This combines the readability of recursion with the speed of iteration. Each Fibonacci number is now only calculated once. The complexity becomes O(n).

FAQs

Q: Why does my program print weird negative numbers for a large number of terms?

A: You’re overflowing the integer type. A standard int can only hold numbers up to a certain size. Fibonacci numbers get very large, very fast. The 47th Fibonacci number is already too big for a standard 32-bit signed int.

Solution: Use a larger data type like long long int to store the numbers. Even that will overflow eventually (around the 93rd number). For truly huge numbers, you’d need a bignum library.

Q: My recursive code is super slow. Why?

A: Because it’s re-calculating the same values over and over. Look at the function call tree for fib(5). You’ll see fib(2) is calculated three times. This redundancy makes the complexity exponential (O(2^n)). Use the iterative (loop) or memoized version for any serious use.

Q: Which method is the best?

A: For simplicity and performance, the iterative for loop is the best. It’s easy to understand and efficient. The memoization approach is also excellent and a good introduction to dynamic programming. The pure recursive solution is mostly for academic purposes to demonstrate the concept of recursion.

Also Read:

• C Interview Questions and Answers
• Data Structures using C
• Armstrong Number in C
• Top C Projects
• Fibonacci Series in Java
• Fibonacci Series in C