You are viewing a single comment's thread. Return to all comments →
Three different JavaScript solutions
Recursive (This is supposed to be the way we're solving it. Linear time and space complexity)
const fibonacci = (n, cache = {}) => { if (n < 0 || n === undefined) return null; if (n < 2) return n; if (cache[n]) return cache[n]; cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache); return cache[n]; };
Iterative (Better solution since it has a constant space complexity but still has linear time complexity)
const fibonacci = n => { let previous = 0; let current = 1; if (n < 0 || n === undefined) return null; if (n < 2) return n; for (let i = 1; i < n; i++) { let temp = current; current = current + previous; previous = temp; } return current; };
And Binet's formula / Golden Ratio (Super efficient constant time AND space complexity)
const fibonacci = n => { if (n < 0 || n === undefined) return null; return Math.round(Math.pow(((1 + Math.sqrt(5)) / 2), n) / Math.sqrt(5)); };
Seems like cookies are disabled on this browser, please enable them to open this website
Recursion: Fibonacci Numbers
You are viewing a single comment's thread. Return to all comments →
Three different JavaScript solutions
Recursive (This is supposed to be the way we're solving it. Linear time and space complexity)
Iterative (Better solution since it has a constant space complexity but still has linear time complexity)
And Binet's formula / Golden Ratio (Super efficient constant time AND space complexity)