How to find nth Fibonacci number using Javascript with O(n) complexity

Trying really hard to figure out how to solve this problem. The problem being finding nth number of Fibonacci with O(n) complexity using javascript.

I found a lot of great articles how to solve this using C++ or Python, but every time I try to implement the same logic I end up in a Maximum call stack size exceeded.

Example code in Python

MAX = 1000

# Create an array for memoization
f = [0] * MAX

# Returns n'th fuibonacci number using table f[]
def fib(n) :
        # Base cases
        if (n == 0) :
                return 0
        if (n == 1 or n == 2) :
                f[n] = 1
                return (f[n])

        # If fib(n) is already computed
        if (f[n]) :
                return f[n]

        if( n & 1) :
                k = (n + 1) // 2
        else : 
                k = n // 2

        # Applyting above formula [Note value n&1 is 1
        # if n is odd, else 0.
        if((n & 1) ) :
                f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
        else :
                f[n] = (2*fib(k-1) + fib(k))*fib(k)

        return f[n]


// # Driver code
// n = 9
// print(fib(n))

Then trying to port this to Javascript

const MAX = 1000;
let f = Array(MAX).fill(0);
let k;

const fib = (n) => {

    if (n == 0) {
        return 0;
    }

    if (n == 1 || n == 2) {
        f[n] = 1;

        return f[n]
    }

    if (f[n]) {
        return f[n]
    }

    if (n & 1) {
        k = Math.floor(((n + 1) / 2))
    } else {
        k = Math.floor(n / 2)
    }

    if ((n & 1)) {
        f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
    } else {
        f[n] = (2*fib(k-1) + fib(k))*fib(k)
    }

    return f[n]
}

console.log(fib(9))

That obviously doesn’t work. In Javascript this ends up in an infinite loops. So how would you solve this using Javascript?

Thanks in advance

Answer

The problem is related to scope of the k variable. It must be inside of the function:

const fib = (n) => {
    let k;

You can find far more good implementations here list

DEMO

Advertisement

Answer