Fibonacci Series Program in C

What is Fibonacci Series?

Look at the below sequence :

We have seen this above, can you see a pattern in it?

In this, the first term is 0 and the second term is 1, and all the remaining terms that we have are the result of the addition of their previous two terms.

For example, the eighth term is 13, which is proceeded by 5 and 8, whose sum is 13, and hence the eighth number is calculated as 13. i.e,

Mathematically we can simply represent it as

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

where F is the fibonacci function having base values $F(0) = 0$ and $F(1) = 1$

In theory, this sequence can continue to infinity by using the same above formula.

Program To Print Fibonacci Series In C Using Recursion

Recursion simply means when a function repeatedly calls itself.

In Fibonacci series problems, we can use this approach to find our required sequence, how?

• We will write a function that will take an integer as an input (the position in the Fibonacci series whose element we want to display) and will return the element at that position
• In this function, we will have an if-else-if ladder
• If the input will be 0 i.e., the element at the 0th position, we will return 0
• If the input will be 1 i.e., the element at 1st position, we will return 1
• else we will recursively call the fibonacci() function again twice and will pass arguments by decreasing the num variable we initially received in that specific call by 1 and 2 respectively and will be adding the function calls
• This process will keep repeating till we get to our base condition of $F(0) = 0$ and $F(1) = 1$ and the function will finally return by adding each of the returned values by each call, and finally we will get our required number

Let's go through the code, then we will understand each line one by one

Program to find fibonacci series in c using recursion:

Input:

Output:

To simplify things, let's have a look at the below recursion tree, and let's try to understand how these function calls happened in real

An image explaining how fibonacci series in c using recursion works:

A Quick Explanation:

• fib(5) is breaking down into fib(4) and fib(3)
• left fib(4) is breaking into fib(3) and fib(2) and right fib(3) is breaking into fib(2) and fib(1)
• This process keeps going till we reach the base condition of fib(1) i.e., value 1 or fib(0) i.e., value 0 in both the directions and thereafter finally each call returns to its parent who has called them by getting added and finally we get the value of fib(5)

Time complexity to find a Fibonacci series element using the recursion approach is $O(2^n)$. The reason is as with each call the function is breaking down into two child calls and then again into two more child calls for each specific child, and hence the time complexity here using the recursion approach will be $O(2^n)$, as it is growing with respect to the power of 2.

Space complexity using recursive approach will be $O(N)$. As in recursion, the space required is proportional to the maximum depth of the recursion tree, and it is N i.e. num in our case, so the space complexity will be $O(N)$.

Till now, we have understood how to find fibonacci series in c using recursion; now let's have a look at its iterative approaches.

C program To Print Fibonacci Series Using Iterative Method

This is another way through which we can write the program for Fibonacci numbers. This is a better way if we are talking from the point of space and time complexity (don't bother if you have no idea what these terms are), In simple words, space complexity means how much extra space a program will take if we keep increasing the input size i.e., from asking for 8th Fibonacci number to asking about 80th number. Same with the time complexity, the time which the program takes to compute the 8th Fibonacci number vs 80th vs 800th Fibonacci number i.e., at what rate does the time taken by the program increase or decrease is its time complexity

In the above recursion tree diagram where we calculated the fibonacci series in c using the recursion method, we can see that, to calculate fib(5), we are calculating fib(4), fib(3), fib(2), fib(1), and fib(0) multiple times, which indeed will affect the resources the program will use (be it time or space)

You may think it's just a small program, and we sometimes ourselves declare and initialize 4, 5 unnecessary variables in our program and we do not use them, so the same is happening here too, how much extra space will it take?

Your point is valid, but when we talk about an efficient program then we do not discuss 5, 6, or 10 inputs, we there talk about a very large input i.e., it may be in lakhs or millions or even more.

So there will almost be so much of unnecessary function calls that it will not be possible for normal systems to process them.

Let's understand how we will do it :

Unlike recursion, where we went level by level backwards and once reached the base value, we returned it and kept adding those returned values to their parent functions and finally we get our required number.

Instead of that, here we will start with the base value itself, and we will plan on getting the next number by adding the previous two values right away, seems simple, and in this way, we will get our required element.

Now, let's look at the code:

Input:

Output:

This technique is also called the Dynamic Programming way As this method has optimized the redundant function calls that are made while going with the recursive approach, which resulted in a more time and space-efficient program

We can modify the above code to be more efficient using the space-optimized method :

Here, instead of creating a whole new array which we did in the above method, we will just store the previous two elements of a number, as that is all that we need to get to the successive element, and hence a lot of memory can be saved.

Explanation:

Here we are doing exactly as same as we did above, but just with one simple modification, now we are storing the previous two values as that is all we need to get our next term, and in this way, we can optimize the space used by our program even more.

Time complexity using an iterative approach is $O(N)$ As we are simply just adding the proceeding two elements of the sequence to get the next element, and hence are only iterating N times

Space complexity using an iterative approach will be $O(1)$ Because here we are working with only three variables, and processing them, again and again, to get F(4) as well as F(40) which means the space required is going to be constant