C Program to Print Nth Fibonacci number

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.

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 nth 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 for the complete tutorial series.

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

All examples are hosted on Github.

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.
Do not forget to share and Subscribe.
Happy coding!! 😊

Recommended -

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x