Last active
October 12, 2021 15:48
-
-
Save kishan-dhankecha/920eb5f7907f279e957f139c08d5c024 to your computer and use it in GitHub Desktop.
Fibonacci function with memoization [JAVASCRIPT]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// Write a function 'fib(n)' that takes in a number as an argument. | |
/// The function should return the n-th number of the Fibonacci sequence. | |
/// The 1st and 2nd number of the sequence is 1. | |
/// To generate the next number of the sequence, we sum the previous two. | |
/// fib(n): 1, 1, 2, 3, 5, 8, 13, 21, 34, | |
const fib = (num, memory = {}) => { | |
// Check in memory. | |
if (num in memory) return memory[num]; | |
// Return obvious values to stop recursion. | |
if (num <= 1) return num; | |
// Store current value in memory. | |
memory[num] = fib(num - 1, memory) + fib(num - 2, memory); | |
// Return value. | |
return memory[num]; | |
} | |
console.log(fib(50)); // prints => 12586269025 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment