Fibonacci Number

Difficulty: Easy · Topic: Recursion

The Fibonacci sequence starts F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n ≥ 2. Return F(n).

A naive recursion is O(2ⁿ) — prefer an iterative or memoised O(n) solution.

Examples

fib(0)
→ 0

fib(1)
→ 1

fib(10)
→ 55

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.