Algo Corner: Nth Fibonacci (2024)

Welcome Back to Algo Corner! This is my little corner of the internet to teach you and me about different algorithm concepts and break down how algorithms work in a fundamental manner. This will all be in Javascript with ES6 formatting.

DISCLAIMER: I AM NO EXPERT AND STILL LEARNING. If you find an error in my algorithm or math please let me know and let it be a teachable moment rather than a sarcastic or self-righteous one.

Today, I will be covering the natural structure of nature, the fibonacci sequence, and how to get the nth fibonacci. I know I promised a binary tree problem, but I found learning some Dynamic Programming principles important, so I thought I would share.

The Fibonacci sequence is a series of numbers that have a special relationship to each the prior two numbers. The math behind it is essentially the sum of the two prior numbers in the sequence equals the current number. For example, lets set Fibonacci Sequence to f, and any place in the sequence is n, if we want to get f(nth place) we would add f(n-1) and f(n-2). Mathematically, it would look like f(n-2)+f(n-1)=f(n). Remember this, it is important! Let’s look at the first few numbers in the sequence and get an understanding.

We have 2 base cases to start our sequence off. 0 and 1, and after that the magic happens. Note: Sometimes they will start with 1, but I like to start with 0, it is personal preference. Basically, the current f(n) shifts over to f(n-1), and f(n-1) becomes f(n-2), and the cycle continues.

The Fibonacci sequence is defined as follows: the first number of the sequence is 0, the second number is 1, and the nth number is the sum of the (n-1)th and (n-2)th numbers. Write a function that takes in an integer n and returns the nth Fibonacci number.(In non-math terms, take a number and return at what number comes back in the sequence at that count.)

Important note: the Fibonacci sequence is often defined with its first two numbers as F0 = 0 and F1 = 1. For the purpose of this question, the first Fibonacci number is F0; therefore, getNthFib(1) is equal to F0, getNthFib(2) is equal to F1, etc..

Sample

n = 2f(1) = 0
f(2) = 1Answer is f(2)'s value or 1n = 6f(1) = 0
f(2) = 1
f(3) = 1
f(4) = 2
f(5) = 3
f(6) = 5

There are 2 ways we are going to solve this problem. The straight recursive method and the memoized recursive method.

const getNthFib = (n) => {
 if(n === 1) return 0
 if(n === 2) return 1
 return getNthFib(n-1) + getNthFib(n-2)
}

Key Element(s) of Method 1

Recursion: Welcome to Dynamic Programming! Recursion is a thing that really freaks people out. It is basically the function calling itself. Whoa Whoa Whoa! How can it call itself if the function is still running?!!? The short of it is that this new sub-function or subroutine will run and put the function it was called in on hold. This is especially true of single-threaded languages like javascript. But how do end this continuous function call and not end up with an infinity paradox a la stack overflow? We use something called a base case that you set which stops the recursion calls. This will then trigger all the subroutines to return the data to the function below it on the stack until you reach the original function where you return all the computational data each subroutine/sub-function did and have your answer.

What is happening in the code?

We will be going through the whole function recursive calls and all! I will draw it out so we can make sense of it visually!

f(6) = f(5) + f(4) and recursion go!

We can see that our base cases of f(1) returns 0 and f(2) returns 1. When it gets all passed up we are adding it up. I would recommend drawing it out the same way I did so you can get a sense of how fibonacci works with recursion.

However, this is a lot of work! As the old adage goes ‘Work smart, not hard!’ Why do we need to keep calling the same recursive calls on the same repeating f(n)’s. If only there was some way to store that data with a quicker run time and SOBO(Save Our Big O)

const getNthFib = (n, cache = {1:0, 2:1}) => {
 if(n in cache){
 return cache[n]
 } else {
 cache[n] = getNthFib(n-1)+getNthFib(n-2);
 return cache[n]
 }
}

Key Element(s) of Method 2

Memoization: Memoization is using an object to store an input and out. The input would be the key and the output would be the value. The one caveat to this is we have to make sure our input and output are consistent no matter the number(s) we plop into the given function. This is super helpful because it gives a run time of O(1) when we are looking up something we have already seen.

What is happening in the code?

We have added a cache/hash/memoize to our function! This helps us by storing values we have seen before and making them accessible really quickly. We have to populate it with our base cases though. If you recall in the beautiful recursive drawing above, we are calling the same things over and over again, when we have already seen it. If we store what we have seen before it will end up looking more like this:

See how many steps that cuts out, because we can now access it on our cache?!?! This is why I love programming! HAWT DAMN! Our cache will look like this at the end:

cache = {
1: 0,
2: 1,
3: 1,
4: 2,
5: 3,
6: 5
}

Just a re-usable and faster way to access fibonacci’s sequence, once we have seen the f(n) already.

Important Note:

When we want to pass along something like a cache down a recursive function, we should pass it as an argument. If we create the cache in the original function with let, const, or var declaration, and then add something to the cache, when we call the function recursively and enter the new sub-function, it will reset to the original cache declared in the OG function.

Method 1:

Our time complexity is O(2^n) because with each recursive call we are calling 2 more functions, unless we hit a base case on one of the recursive calls.

Our space complexity is O(n) because and this is important in recursion we are using the call stack(remember the plates) and that takes up memory. The stack is a data structure so it uses memory n times, where n is the number of recursive calls.

Method 2:

Our time complexity is O(n) because we are calling each recursive case at least once before it gets added to the cache.

Our space complexity is O(n) because of the same reason as method 1, the call stack!

We will be going over Find Three Largest Numbers.

If you want to learn more about recursion please click this link. HA!