Level 1: Basics · Exercise 13 of 76 · Free

Fibonacci numbers

A JavaScript exercise from Scriptdrill. Solve it with a code editor in your browser that runs your function against example and hidden tests, and it is checked the moment you submit.

The task

Return the `n`th Fibonacci number, counting from 0: `fib(0)` is 0, `fib(1)` is 1, and every later number is the sum of the two before it, so the sequence runs 0, 1, 1, 2, 3, 5, 8. `n` is a whole number from 0 to 78. It has to be fast for large `n`: the plain version that calls itself twice takes far too long for `fib(50)`.

What this exercise teaches

The textbook recursion recomputes the same values again and again, so its running time doubles with every step. A loop that carries the last two values does the same work in n steps. Above n = 78 the results no longer fit exactly in a JavaScript number, which is where BigInt comes in.

A hint if you get stuck

Keep only the last two numbers in two variables and step forward `n` times in a loop. A recursive version works too if it remembers the results it has already computed.