Fibonacci Series in C – Iterative, Recursive, and Array Methods

The Fibonacci series in C is a sequence where each number is the sum of the two preceding ones, starting from 0 and 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

This page covers three approaches — iterative series printing, a recursive function, and a side-by-side comparison of their time and space complexity.

Fibonacci Series in C — Iterative (Print First N Terms)

The iterative approach is the most practical: two variables track the previous two values and each iteration computes the next:

#include <stdio.h>

int main(void)
{
    int n, i;
    long long a = 0, b = 1, next;

    printf("How many Fibonacci terms? ");
    scanf("%d", &n);

    printf("Fibonacci series:\n");
    for (i = 0; i < n; i++) {
        printf("%lld ", a);
        next = a + b;
        a    = b;
        b    = next;
    }
    printf("\n");
    return 0;
}

How to Compile and Run

gcc -Wall -o fibonacci fibonacci.c
./fibonacci

Sample Output

How many Fibonacci terms? 10
Fibonacci series:
0 1 1 2 3 5 8 13 21 34

How many Fibonacci terms? 5
Fibonacci series:
0 1 1 2 3

Recursive Fibonacci in C

The recursive definition maps directly to the mathematical formula F(n) = F(n−1) + F(n−2):

#include <stdio.h>

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

int main(void)
{
    int n, i;
    printf("How many Fibonacci terms? ");
    scanf("%d", &n);

    printf("Fibonacci series:\n");
    for (i = 0; i < n; i++)
        printf("%lld ", fibonacci(i));
    printf("\n");
    return 0;
}

Recursion trace for fibonacci(5):

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2) → fibonacci(1)+fibonacci(0) = 1
│   │   └── fibonacci(1) = 1   → 2
│   └── fibonacci(2) → 1       → 3
└── fibonacci(3) → 2            → 5

Notice that fibonacci(2) and fibonacci(3) are computed multiple times. This is the exponential overlap that makes naive recursion slow for large n.

Fibonacci Using Array (Memoization)

Storing previously computed values eliminates the repeated work and reduces time to O(n):

#include <stdio.h>
#define MAX 50

int main(void)
{
    long long fib[MAX];
    int n, i;

    printf("How many Fibonacci terms (max %d)? ", MAX);
    scanf("%d", &n);

    if (n > MAX) { printf("Too many terms.\n"); return 1; }

    fib[0] = 0;
    if (n > 1) fib[1] = 1;

    for (i = 2; i < n; i++)
        fib[i] = fib[i-1] + fib[i-2];

    printf("Fibonacci series:\n");
    for (i = 0; i < n; i++)
        printf("%lld ", fib[i]);
    printf("\n");
    return 0;
}

Fibonacci Number Table

Time and Space Complexity

The naive recursive version is exponential because it recomputes the same subproblems. For n = 40 it performs over 300 million function calls. Use the iterative or memoized version for any practical application.

What This Program Teaches

• The two-variable rolling update pattern — a space-efficient way to maintain a sliding window over two consecutive values
• Why clean recursive code can hide exponential performance — the code looks simple but the call tree is massive
• Memoization: storing results of expensive function calls avoids recomputation
• The long long type for large integers — int overflows at F(46) = 1,836,311,903 on 32-bit systems

Related Programs

• Factorial Program in C — Iterative and Recursive
• Palindrome Program in C
• C Aptitude Questions and Answers

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Recursion, arrays, and loops are all introduced in the first chapters of The C Programming Language by Kernighan & Ritchie — still the best way to learn C from first principles. Also on Amazon.com.