Tag: fibonacci

Categories
Dynamic Programming Leetcode Recursion

Fibonacci (Recursion)

function fib(x) {
    let cache = {}
    function fibInternal(n) {
        if(n == 0) return 0;
        if(n <= 2) return 1;
        if (cache[n]) return cache[n];

        const result = fibInternal(n - 1) + fibInternal(n - 2);
        cache[n] = result;
        return result;
    }

    return fibInternal(x)
}
Categories
Leetcode

Fibonacci (Iterative)

function fib(n) {
    if(n === 0) return 0;
    if(n <= 2) return 1;

    let x = 1, y = 2;
    for(let i = 3; i < n; i++) {
        let oldX = x;
        x = y;
        y = y + oldX;  /*?.*/
    }

    return y; 
}