Before we proceed, make sure you know what the Fibonacci Series is. The Fibonacci sequence is a type series where each number is the sum of the two that precede it. It starts from 0 and 1 usually. The Fibonacci sequence is given by 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on. The numbers in the Fibonacci sequence are also called Fibonacci numbers.
The nth Fibonacci number is calculated by adding thee (n-1)th and (n-2)th number of the Fibonacci Series.
Let's write a function called "fib" that takes in two parameters -
n: The position in the Fibonacci sequence for which we want to find the value.
memo: An object used to store previously computed Fibonacci values to avoid redundant calculations.
function fib(n, memo) {
memo = memo || {}
if (memo[n]) {
return memo[n]
}
if (n <= 1) {
return 1
}
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
}Let us see what each line of the function implies:
memo = memo || {}: If memo is not provided (or is undefined or null), it initializes memo as an empty object. This ensures that memo is always a valid object.
if (memo[n]) { return memo[n] }: This line checks if the Fibonacci number for the given n has already been computed and stored in memo. If it exists (memo[n] is truthy), the function returns this precomputed value, avoiding further computation.
if (n <= 1) { return 1 }: This handles the base cases of the Fibonacci sequence. By definition, fib(0)=1fib(0)=1 and fib(1)=1fib(1)=1. The function returns 1 when n is 0 or 1.
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo): If the value for n is not already in memo and n is greater than 1, the function computes it recursively. The result is the sum of the Fibonacci numbers for n - 1 and n - 2.
This computed value is then stored in memo[n] before being returned. Storing the value ensures that future calls to fib with the same n can return the precomputed result, thus reducing the time complexity.
The best case time complexity of this is O(1), while the worst case is O(n).