Fibonacci Number
Easy · Backtracking · Math · Recursion · Memoization · Dynamic Programming
Problem
The Fibonacci sequence starts with F(0) = 0 and F(1) = 1, and every later term is the sum of the two terms before it: F(n) = F(n - 1) + F(n - 2) for n > 1.
Given n, return F(n).
Examples
Input: n = 5 Output: 5
The sequence runs 0, 1, 1, 2, 3, 5, so F(5) is 5.
Input: n = 10 Output: 55
F(8) = 21 and F(9) = 34, and their sum is 55.
Input: n = 0 Output: 0
The first term is defined as 0.
Constraints
- 0 <= n <= 30
Approaches
- Baseline: plain recursion — time O(φⁿ), about O(1.62ⁿ), space O(n) call stack
Follow-up
For n up to 10^18 (with the answer taken modulo a prime), a loop is too slow. The pair (F(n+1), F(n)) is a 2×2 matrix power applied to (1, 0), so squaring the matrix gives the answer in O(log n). The "fast doubling" identities F(2k) = F(k)·(2F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)² do the same with less work.
Related problems
Start free on Cariara · Coding problems · System design studio
