Fibonacci series number in C – Complete guide with example

Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. In mathematical terms, the Fibonacci sequence is defined by the recurrence relation:

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

with initial conditions:

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

In this blog post, we will explore different methods to generate Fibonacci series numbers in C programming language. We will discuss the following techniques:

Using loops
Using recursion
Using dynamic programming

Using Loops

A simple and straightforward way to generate Fibonacci series numbers is by using loops. We can use either a for loop or a while loop to achieve this. Let's start with the for loop.

Using for loop

Here's the C code to generate the first n Fibonacci numbers using a for loop:

#include <stdio.h>

int main() {
    int n, num1 = 0, num2 = 1, nextNum;

    printf("Enter the number of Fibonacci numbers to generate: ");
    scanf("%d", &n);

    printf("Fibonacci Series: ");

    for (int i = 1; i <= n; ++i) {
        printf("%d, ", num1);
        nextNum = num1 + num2;
        num1 = num2;
        num2 = nextNum;
    }

    return 0;
}

In this code, we first initialize num1 and num2 with the initial Fibonacci numbers, 0 and 1. Then, we calculate the next number in the series by adding num1 and num2. We update the values of num1 and num2 for the next iteration and continue the process.

Using while loop

Here's the C code to generate the first n Fibonacci numbers using a while loop:

#include <stdio.h>

int main() {
    int n, num1 = 0, num2 = 1, nextNum, count = 0;

    printf("Enter the number of Fibonacci numbers to generate: ");
    scanf("%d", &n);

    printf("Fibonacci Series: ");

    while (count < n) {
        printf("%d, ", num1);
        nextNum = num1 + num2;
        num1 = num2;
        num2 = nextNum;
        count++;
    }

    return 0;
}

The logic for generating the Fibonacci series using a while loop is the same as the for loop. We just change the loop structure to a while loop and use a counter variable count to keep track of the number of Fibonacci numbers generated.

Using Recursion

Another way to generate Fibonacci series numbers is by using recursion. In this approach, we define a recursive function that returns the nth Fibonacci number.

Here's the C code to generate the first n Fibonacci numbers using recursion:

#include <stdio.h>

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

int main() {
    int n;

    printf("Enter the number of Fibonacci numbers to generate: ");
    scanf("%d", &n);

    printf("Fibonacci Series: ");

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

    return 0;
}

The fibonacci function calculates the nth Fibonacci number using the recurrence relation mentioned earlier. The base case of the recursion is when n is 0 or 1, in which case the function returns n directly. For other values of n, the function calls itself recursively with n-1 and n-2 as arguments and returns their sum.

Using Dynamic Programming

The recursive approach can be quite slow for large values of n due to redundant calculations. To optimize the performance, we can use dynamic programming techniques like memoization or tabulation. In this section, we will discuss the tabulation method.

Here's the C code to generate the first n Fibonacci numbers using dynamic programming (tabulation):

#include <stdio.h>

void fibonacci(int n) {
    int fib[n + 2]; // Array to store Fibonacci numbers
    fib[0] = 0;
    fib[1] = 1;

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

    printf("Fibonacci Series: ");

    for (int i = 0; i < n; i++) {
        printf("%d, ", fib[i]);
    }
}

int main() {
    int n;

    printf("Enter the number of Fibonacci numbers to generate: ");
    scanf("%d", &n);

    fibonacci(n);

    return 0;
}

In this code, we first create an array fib[] to store the Fibonacci numbers. We then initialize the first two elements of the array with the initial Fibonacci numbers, 0 and 1. Next, we calculate the remaining Fibonacci numbers iteratively using a for loop and store them in the array. Finally, we print the first n Fibonacci numbers from the array.

FAQ

What is the time complexity of the loop method?

The time complexity of the loop method is O(n) as we iterate through the loop n times.

What is the time complexity of the recursive method?

The time complexity of the recursive method is O(2^n) due to the exponential growth of the function calls.

What is the time complexity of the dynamic programming method?

The time complexity of the dynamic programming method is O(n) as we iterate through the loop n times. However, this approach is more efficient than the loop method as it avoids redundant calculations.

Can we generate negative Fibonacci numbers?

Yes, we can generate negative Fibonacci numbers by extending the sequence to negative indices. The formula for negative Fibonacci numbers is:

F(-n) = (-1)^(n+1) * F(n)

Are there any real-world applications of Fibonacci series?

Fibonacci series has various applications in computer science, mathematics, and nature. Some of the real-world applications include computer algorithms, data structures, financial market analysis, and modeling natural phenomena like the arrangement of leaves on a stem or the growth patterns of seashells.