Fibonacci Series Program in C
Fibonacci series is a sequence of Integers that starts with 0 followed by 1, in this sequence the first two terms i.e. 0 and 1 are fixed, and we get the successive terms by summing up their previous last two terms. i.e, the series follows a pattern that each number is equal to the sum of its preceding two numbers
Mathematically it can be written as :
where F is the Fibonacci function having base values and
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
where F is the fibonacci function having base values and
In theory, this sequence can continue to infinity by using the same above formula.
Note : In some resources, the Fibonacci series starts from 1 as well, but in most places, we will have the Fibonacci sequence starting from 0 only.
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 and 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:
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 . 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 , as it is growing with respect to the power of 2.
Space complexity using recursive approach will be . 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 .
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:
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.
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 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 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
- Fibonacci numbers are simply a sequence of integers that starts from 0 followed by 1, and after that, every successive element is obtained by addition of its proceeding two terms
- We can use recursion as well as the iterative method to work with Fibonacci series
- Use of the iterative method is better time and space-optimized
- Fibonacci series works on the simple principle of
Join our expert-led Dynamic Programming Course to master advanced problem-solving techniques and enhance your programming prowess.