fibonacci

Medium · Recursion · 3 test cases

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Write a recursive function that returns the nth Fibonacci number (0-indexed).

Examples

fibonacci(2) → 1
fibonacci(9) → 34
fibonacci(0) → 0

Starter code

function fibonacci(n) {

}

Complexity of the optimal solution

Time O(2^n), space O(n). This is a classic tree recursion. The function branches into two calls for each number, leading to an exponential number of computations. The time complexity is O(2^n). The maximum depth of the call stack is n, so the space complexity is O(n).

Solve fibonacci in the browser