Memoized Fibonacci
We'll add yet another tool to our toolbelt in this lesson. We'll learn memoization, a technique of storing data that has already been computed for later use.
Fibonacci
We’ll start with the simple version and create the advanced version further down.
Instructions
Write a function that will take a positive integer n and return an array of length n containing the Fibonacci sequence.
Input: Integer > 0
Output: Array of Numbers
Examples
fibonacci(4); // -> [1, 1, 2, 3]
fibonacci(6); // -> [1, 1, 2, 3, 5, 8]
fibonacci(8); // -> [1, 1, 2, 3, 5, 8, 13, 21]
Press + to interact
function fibonacci(n) {// Your code here}
Solution 1
Press + to interact
function fibonacci(n) {const seq = [1, 1];if(n < 2) {return seq.slice(0, n);}while(seq.length < n) {const lastItem = seq[seq.length - 1];const secondLastItem = seq[seq.length - 2];seq.push(lastItem + secondLastItem);}return seq;}
How it Works
We store the sequence in seq
. In the loop, we add up the previous two values in the array and push the sum into the array. We run the loop until we have the array length we want.
Time
Time complexity is: ...
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy