Adding Fibonacci Numbers With Using Recursion Function
What is Fibonacci Sequence?
The concept of mathematics, in its essence, is closely linked with the patterns and structures of nature. One such pattern that is ubiquitous in nature is the Fibonacci sequence. This sequence, consisting of numbers such as 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55, is generated by adding the two preceding numbers to obtain the next number in the sequence. For instance, 1+1=2, 1+2=3, 2+3=5, and so on.
The Fibonacci sequence was first described by mathematicians in India about 1300 years ago. Still, it gained prominence in the West when Leonardo of Pisa, also known as Fibonacci, introduced it in his book Liber Abaci in 1202. Fibonacci is also responsible for introducing Arabic numerals to Europe.
Interestingly, when you divide any Fibonacci number by the one preceding it in the sequence, especially the larger ones, the result is approximately the same number, known as the golden ratio. This ratio has been observed in many natural phenomena, such as the spiral patterns of shells, the arrangement of leaves on a stem, and the proportions of the human body.
144/89, 1597/987
You get the same number:1.618Today, We will see a recursion method for adding up Fibonacci Numbers.
Fibonacci Numbers With Recursion
The Problem:
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.Given n, calculate F(n).
Example 1:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.Example 2:
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.Example 3:
Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.My Solution
Actually, we have a great tip from the question which is mentioning we should use recursion to solve this problem. If you look up the problem description you will see the part which includes as follows.
F(0) = 0, F(1) = 1It’s basically given us our base condition in the problem description. It means we can get the smallest input if the (n 0) or (n 1) then we return 0. That’s how we will start to implement our function first.
var fib = function(n) {
if(n === 0 || n ===1){
return n;
}If n(0) We will return 0 or || If n(1) we will just return 1,
But we also need an edge case if n is not 0 or n is not 1; That’s where the calculation to answer came up in the game. In the question also included that how we will calculate the edge case. They also told us how to implement it in the question description.
F(n) = F(n - 1) + F(n - 2), for n > 1.It says to get F(n) You just need to do F(n-1) and add up F(n-2). And as you see this line of code is recursive.
Because on the left side, you see function F(n) and proper side function F(n) |function F(n) again. To solve the F(n), You should call again the function F(n) and again and sum the answers after summing the function the answer(function F(n) + function F(n) ) is on the left side. It’s obviously a Recursion Function.
We just need to return
return fib(n-1) + fib(n-2);Full Solution
//fib = 0,1,2,3,4,5....,N
//Ans = 0,1,1,2,3,5....,? var fib = function(n) {
if(n === 0 || n ===1){
return n;
}
return fib(n-1) + fib(n-2);
}
Let’s take a closer look for deep understanding
Example 2:
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.This example actually asking us;
if the input is n =2 ;
We should get the Output : 1;
What it is actually mean?
First step
fib(2) = fib(1) + fib(0) which means how we calculate to get the number fib(2) based on Fibonacci Sequence.
fib = 0,1,2,3,4,5....,N
Ans = 0,1,1,2,3,5....,?But in the function which we created fib(2) = fib(2–1) + fib(2–2)
If we see input is n(2)
We know the answer is calculation of fib(2–1) + fib(2–2)
If we breakdown one more level its actually look like this;
fib = 0,1,2,3,4,5....,N.
(2)= 0+1,1,2,3,5....,? fib(1) + fib(0)fib (2) = fib(1) + fib(0)
We already got the answer in our base case solution as following code;
var fib = function(n) {
if(n === 0 || n ===1){
return n;
}
If n(0) We will return 0 or || If n(1) we will just return 1,
0 + 1 = 1
if (n) = fib(0) + fib(1) = 1
If we just point of how this function works we can think like visual below explain like if input as fib(3)
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
fib = 0,1,2,3,4,5....,N
(2)= 0,1+1,2,3,5....,? fib(1) + fib(2)When n(3 ) We basically calling this part of function.
return fib(n-1) + fib(n-2);
// 1 + 1 = 2I know it’s a little bit tricky because when you go fib(3) You also have to go one level down and get the result of fib(2) then fib(1) and sum. After summing them. You will get the fib(3).
Time and Space Complexity
When we asked about time and space complexity for our function.
Time Complexity : 0(2^N)
Space Complexity: 0(N)
Actually Time complexity of the function is really large 0(2^N)
If n= 4 -> 2 ^ 4 = 16
If we do 16 operations it’s really too much. It’s actually not the best solution for time complexity. What we could do, we can store the result. To avoid time complexity problem we can implement Dictionary.
class Solution {// fib = 0, 1, 2, 3, 4, 5, ..., N// ans = 0, 1, 1, 2, 3, 5, ..., ?// fib(2) = fib(2-1) + fib(2-2)// fib(2) = fib(1) + fib(0)// = 1 + 0 = 1/*fib(4) = fib(3) + fib(2)/ \fib(3)=2 done fib(2)/ \ 2 is in cache!fib(2)=1 + fib(1)=1/ \fib(1)=1 + fib(0)=0time: O(N), n=4 -> 2^4 = 16space: O(N)*/Map<Integer, Integer> cache = new HashMap<>();// key: N, value: fib(N) answerpublic int fib(int n) {// base case: we already know the answer for nif (n == 0 || n == 1)return n;// base case: already solved answer for nif (cache.containsKey(n))return cache.get(n);// we need to calculate the answerint answer = fib(n - 1) + fib(n - 2);// store this answer for ncache.put(n, answer);return answer;}}
