Nth Fibonacci numbers can be found and printed using C, C++, Java, Python, and many more programs. 

Programmers use various approaches in various programs to find and print nth Fibonacci numbers. 

In this blog, we will discuss different approaches to the C program in detail to find and print output from the Fibonacci series in C.

However, if you are a new learner about to embark on a journey into the world of C programming language, you must go through all the approaches to find and print the nth number in the Fibonacci sequence. 

However, before you learn the approach of the C program, it is imperative to know about the Fibonacci series in C.

Fibonacci Series in C is the sequence or series where the sum of the previous two numbers is expressed in the following line of numbers. 

The numbers are taken from the list: 0, 1, 1, 2, 3, 5, 8 etc. The initial two integers are always 0 and 1 in the Fibonacci series in C. Now, if the input is n=1, the output will be 1; if the input is n=9, the output will be 34. 

Different Approaches to Find and Print Nth Fibonacci Numbers in C Program

  • Find and Print Nth Fibonacci Numbers: Iterative Approach

In general mathematical language, this recurrence relation: Fn= F(n-1)+F(n-2) expresses the Fibonacci numbers' sequence Fn, for the seed values and F0=0 and F1=1.

// Fibonacci Series using Space Optimized Method

#include <stdio.h>

int fib(int n)

{

int a = 0, b = 1, c, i;

if (n == 0)

return a;

for (i = 2; i <= n; i++) {

c = a + b;

a = b;

b = c;

}

return b;

}


int main()

{

int n = 9;

printf("%d", fib(n));

getchar();

return 0;

}

Your output will be 34, where the time complexity is O(n) and auxiliary space is O (1).

  • Find and Print Nth Fibonacci Numbers: Recursion Approach

In mathematical language, the Fibonacci numbers' sequence Fn is expressed by this recurrence relation: Fn= F(n-1)+F(n-2) for the seed values and F0=0 and F1=1.

You can find the Nth Fibonacci Number utilizing the above-mentioned recurrence relation:

  • If n = 0, then it will return 0. 
  • If n = 1, then it will return 1. 
  • For n > 1, it will return Fn-1 + Fn-2

// Fibonacci Series using Recursion

#include <stdio.h>

int fib(int n)

{

if (n <= 1)

return n;

return fib(n - 1) + fib(n - 2);

}


int main()

{

int n = 5;

printf("%dth Fibonacci Number: %d", n, fib(n));

return 0;

}

The desired output will be 34. The time complexity will be exponential because each function calls 2 different functions. Again, the auxiliary space complexity will be 0(n), for the recursion tree's maximum depth is n. 

  • Find and Print Nth Fibonacci Numbers: Dynamic Approach

From the above approach, let us assume that the figure below is the recursion tree for the given 5th Fibonacci number. 

                        fib(5)  
                    /                \
               fib(4)                fib(3)  
            /        \              /       \
        fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

If you notice the tree, you will see that the method call is performed repeatedly in the recursion approach. 

A programmer can easily optimize the entire process using a dynamic approach in the C program. They will store the calculated Fibonacci numbers and carry out the same quickly. 

Let us assume a tree for the nth number:

                          fib(4)  
                    /                \
               fib(3)                fib(2)  
            /        \              /       \
        fib(2)      fib(1)         fib(1)   fib(0)
        /    \     
  fib(1)   fib(0) 
  

Check out the implementation of the above approach below:

// Fibonacci Series using Dynamic Programming

#include <stdio.h>


int fib(int n)

{

/* Declare an array to store Fibonacci numbers. */

int f[n + 2]; // 1 extra to handle case, n = 0

int i;


/* 0th and 1st number of the series are 0 and 1*/

f[0] = 0;

f[1] = 1;


for (i = 2; i <= n; i++) {

/* Add the previous 2 numbers in the series

and store it */

f[i] = f[i - 1] + f[i - 2];

}


return f[n];

}


int main()

{

int n = 9;

printf("%d", fib(n));

getchar();

return 0;

}

The output will be the same 34 with the same time complexity of O(n) and auxiliary space of O (1).

  • Find and Print Nth Fibonacci Numbers: Nth Power of Matrix

This is a special approach. It relies on the factuality that if a programmer multiplies the matrix M = {{1,1},{1,0}} to itself for n times (in other means, calculate power(M, n)), then they will get the Fibonacci number (n+1) as the given element at the row and the column (0, 0) in its resultant matrix.

  • k will be n/2 if the value of n is taken even

Hence, the Nth Fibonacci Number = F(n) = [2*F(k-1) + F(k)]*F(k)

  • k will be (n + 1)/2 if the value of n is taken odd

Hence, the Nth Fibonacci Number = F(n) = F(k)*F(k) + F(k-1)*F(k-1)

Here's how you can obtain the formula:

Let’s take the determinant on both sides, we will get (-1)n = Fn+1Fn-1 – Fn2 

Moreover, as AnAm = An+m for any A square matrix, the following identities will be derived (they will be derived from two different matrix product coefficients) 

FmFn + Fm-1Fn-1 = Fm+n-1         —————————(1)

Now, put n = n+1 in equation(1),

FmFn+1 + Fm-1Fn = Fm+n             ————————–(2)

If we put m = n in equation(1).

F2n-1 = Fn2 + Fn-12

Put m = n in equation(2)

F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn  ——–

(putting Fn+1 = Fn + Fn-1 )

All we have to do is follow the instructions to get the desired formula. 

Put k = n/2 if the value of n is even

Put k = (n+1)/2 if the value of n is odd

Now, let us implement the entire approach in the following part:

#include <stdio.h>


void multiply(int F[2][2], int M[2][2]);


void power(int F[2][2], int n);


/* function that returns nth Fibonacci number */

int fib(int n)

{

int F[2][2] = { { 1, 1 }, { 1, 0 } };

if (n == 0)

return 0;

power(F, n - 1);

return F[0][0];

}


/* Optimized version of power() in method 4 */

void power(int F[2][2], int n)

{

if (n == 0 || n == 1)

return;

int M[2][2] = { { 1, 1 }, { 1, 0 } };


power(F, n / 2);

multiply(F, F);


if (n % 2 != 0)

multiply(F, M);

}


void multiply(int F[2][2], int M[2][2])

{

int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];

int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];

int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];

int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];


F[0][0] = x;

F[0][1] = y;

F[1][0] = z;

F[1][1] = w;

}


/* Driver program to test above function */

int main()

{

int n = 9;

printf("%d", fib(9));

getchar();

return 0;

}

The output will be as you have wanted, 34. But the time complexity will be O(Log n). The auxiliary space will also be O(Log n) if you consider the function call's stack size. If you do not, the value will be the same as O(1).  

Wrapping up, 

This was a detailed discussion of the method of finding and printing the nth Fibonacci number in the C program. 

However, while using the C program, you must ensure you have the perfect Online C compiler for code conversion.