Solving The Leetcode Question Fibonacci Number
For this blog, I’ll be going over how to solve the Fibonacci sequence problem using Recursion. Note that I’ll be going over this problem using JavaScript!
Here’s a screenshot of the prompt:
The prompt is asking us to create a function that takes in a number n and return the calculated value of F(n). The examples for this prompt do a great job in demonstrating what the inputs and outputs should be for this question. For example 1, we can see that the input value is n = 2, which means that it’s actually F(2). Using the equation provided by the prompt (F(n-1) + F(n-2)), we can see how F(2) will equal to F(1) + F(0) and that turns out to equal 1. For more info on the Fibonacci sequence please check out the resources section at the bottom of this blog!
As I mentioned before, I’ll be solving this problem using Recursion. Recursion is calling a function within itself until a certain condition is reached. Recursion starts from the end and works backwards (top-down approach). Now that I’ve explained the prompt, let’s jump right into pseudo coding. If you didn’t understand the prompt that’s completely fine, hopefully the pseudo code will make more sense! Here’s a screenshot of the pseudo code that I wrote:
The first step is creating a conditional that will return 0 or 1 if n equals 0 or 1. There are many ways to write the conditional, but I chose to write it like this:
Returning n is probably the best way since we want our answer to be more dynamic. It’s better to simply return n rather than returning a number.
The next and last step is returning the equation that I mentioned earlier. At first I was having issues with this because I kept returning (n-1) + (n-2). If the input is 2 then we will get the right answer which is 1 because (2–1) + (2–2) is 1. Now, if our input is 4 we will get (4–1) + (4–2) which is 5. 5 is the incorrect output because F(4) should actually be 3. Here is the correct way to break it down, F(4) is broken down into (4–1) + (4–2), which is now F(3) + F(2). From there F(3) is broken down into (3–1) + (3–2) which now equals F(2) + F(1). Now, F(2) will be broken down into (2–1) + (2–2), and that converts into F(1) + F(0). We know that F(1) + F(0) = 1, so when we add everything up (F(3) + F(2)) that should give us a total of 3. This is why we have to call the function fib() within itself. Here’s a better visual of what I just explained:
Looking at the picture that I drew above, we can find the answer by adding up each F(1), which in this case is 3.
Here’s a screenshot of the full solution:
Here are the outputs for lines 36–39:
Here’s the submission on Leetcode:
I hope this blog was helpful! Please reach out if there are other ways in which this problem can be solved. For more info on Recursions and Fibonacci sequence please check the resources section below.
