C Program to Print Nth Fibonacci number

Hitesh Garg | February 14, 2021 | C Programming Example | No Comments

In this C programming example, we will discuss the Fibonacci numbers and implement the program that prints the nth Fibonacci number in C Language using recursive and other time optimized approach.

Table of Contents

1. Introduction to Fibonacci Sequence

Fibonacci numbers are sequences of numbers in which each number in the sequence is equal to the sum of two numbers before it.

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

In Mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

Fn = Fn-1 + Fn-2

Helpful topics to understand the implementation of this program better are:

2. Recursive C program to print Nth Fibonacci sequence

In this example, we will implement the logic to find the n^th Fibonacci number using the recursive approach, where n is input by the user.

#include <stdio.h>

long fibonacciRecursive(int num)
{
    if (num <= 1)
        return num;
    return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
}

int main()
{
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);

    printf("\nThe %dth fibonacci number is %ld", num, fibonacciRecursive(num));
    return 0;
}

Output
Enter a number: 50
The 50th fibonacci number is 102334155

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.

With this approach, there is a lot of repeated work and hence it takes a lot of time to calculate for bigger numbers. To optimize this we can use another approach with an extra variable to bring the time complexity down to O(n).

3. [Optimized] C program to print Nth Fibonacci sequence

In this example, we will implement the logic to find the nth Fibonacci number using the space and time optimized approach, where n is input by the user.

#include <stdio.h>

long fibonacci(int num)
{
    long a = 0, b = 1, c = 0;
    
    if (num <= 1)
        return num;
    
    for (int i = 2; i <= num; i++)
    {
        c = a + b; // stores previous 2 values of the series i.e. a and b
        a = b;     //copy previous number to its previous number
        b = c;     //copy sum (c) to first previous number
    }
    return b;
}

int main()
{
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);

    printf("The %dth fibonacci number is %ld", num, fibonacci(num));
    return 0;
}

Output
Enter a number: 50
The 50th fibonacci number is 102334155

Time Complexity: T(n) = O(n) which is linear and far better than the recursive approach.

Note: With recursive approach as well we can have a better performance by caching the results for each number but it adds a lot of complexity and also needs more space.

4. Conclusion

In this C Programming example, we have discussed, how to find the nth Fibonacci number with multiple approaches i.e. using a recursive method approach and also with space and time optimized approach.

We have also discussed why the space-optimized approach is better than the recursive approach.

Helpful Links

Please follow C Programming tutorials or the menu in the sidebar for the complete tutorial series.

Also for the example C programs please refer to C Programming Examples.

All examples are hosted on Github.

Recommended Books

An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding

Codingeek