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

Question

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

The same way you would do it by hand. Calculate the next number from the prvious two. No recursion needed. No storing of more than the prvious 2 values needed. — MrSmith42
– MrSmith42, Commented Jan 8, 2018 at 12:39
@iremlopsum Do you know that you can post answer to your own question? — user202729
– user202729, Commented Jan 8, 2018 at 12:45

OmG · Accepted Answer · 2018-01-08 12:54:49Z

3

you can iterate from bottom to top (like tail recursion):

var fib_tail = function(n){
        if(n == 0)
             return 0;
        if(n == 1 || n == 2)
             return 1;
        var prev_1 = 1, prev_2 = 1, current; 
        // O(n)
        for(var i = 3; i <= n; i++)
        {
            current = prev_1 + prev_2;
            prev_1 = prev_2;
            prev_2 = current;
        }
        return current;
 }
 console.log(fib_tail(1000))

edited Jan 8, 2018 at 12:54

answered Jan 8, 2018 at 12:38

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

OmG Over a year ago

@rockstar I mean iterating from bottom to top. Anyhow, removed it.

Engineer · Accepted Answer · 2018-01-08 12:53:39Z

1

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

edited Jan 8, 2018 at 12:53

answered Jan 8, 2018 at 12:43

Engineer

48.9k12 gold badges90 silver badges93 bronze badges

2 Comments

iremlopsum Over a year ago

This the correct answer, thanks, I solved it in a different way initially that works. But you pointed out the correct problem with my code :)

Engineer Over a year ago

I have edited my answer to add a link, that can be helpfull

Alok Deshwal · Accepted Answer · 2020-01-19 07:37:57Z

1

fibonacci number in O(n) time and O(1) space complexity:

function fib(n) {
    let prev = 0, next =1;
    if(n < 0)
        throw 'not a valid value';
    if(n === prev || n === next)
        return n;
    while(n >= 2) {
        [prev, next] = [next, prev+next];
        n--;
    }
    return next;
}

edited Jan 19, 2020 at 7:37

answered Jan 19, 2020 at 7:29

Alok Deshwal

1,1369 silver badges20 bronze badges

Comments

user8897421 · Accepted Answer · 2018-01-08 12:43:08Z

0

Just use two variables and a loop that counts down the number provided.

function fib(n){
    let [a, b] = [0, 1];
    while (--n > 0) {
      [a, b] = [b, a+b];
    }
    return b;
}

console.log(fib(10));

answered Jan 8, 2018 at 12:43

user8897421

Comments

WesleyAC · Accepted Answer · 2021-04-30 03:47:28Z

0

Here's a simpler way to go about it, using either iterative or recursive methods:

function FibSmartRecursive(n, a = 0, b = 1) {
    return n > 1 ? FibSmartRecursive(n-1, b, a+b) : a;
}

function FibIterative(n) {
    if (n < 2) 
        return n;

    var a = 0, b = 1, c = 1;

    while (--n > 1) {
        a = b;
        b = c;
        c = a + b;
    }

    return c;
}

function FibMemoization(n, seenIt = {}) {//could use [] as well here
    if (n < 2) 
        return n;
    if (seenIt[n]) 
        return seenIt[n];

    return seenIt[n] = FibMemoization(n-1, seenIt) + FibMemoization(n-2, seenIt); 
}

console.log(FibMemoization(25)); //75025
console.log(FibIterative(25)); //75025
console.log(FibSmartRecursive(25)); //75025

edited Apr 30, 2021 at 3:47

answered Nov 16, 2019 at 22:59

WesleyAC

5536 silver badges12 bronze badges

Comments

PhiAgent · Accepted Answer · 2021-08-05 18:48:43Z

0

You can solve this problem without recursion using loops, runtime O(n):

function nthFibo(n) {
    // Return the n-th number in the Fibonacci Sequence
    const fibSeq = [0, 1]
    if (n < 3) return seq[n - 1]
    let i = 1
    while (i < n - 1) {
        seq.push(seq[i - 1] + seq[i])
        i += 1
    }
    return seq.slice(-1)[0]
}

edited Aug 5, 2021 at 18:48

answered Aug 4, 2021 at 23:01

PhiAgent

1586 bronze badges

Comments

dota2pro · Accepted Answer · 2022-06-11 13:11:38Z

0

// Using Recursion
const fib = (n) => {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(4)) // 3
console.log(fib(10)) // 55
console.log(fib(28)) // 317811
console.log(fib(35)) // 9227465

answered Jun 11, 2022 at 13:11

dota2pro

7,9548 gold badges51 silver badges87 bronze badges

Collectives™ on Stack Overflow

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

7 Answers 7

1 Comment

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

1 Comment

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related