#509
Fibonacci Number
Easy Recursion → iteration
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the n-th Fibonacci number, where F(0) = 0, F(1) = 1 and each next number is the sum of the two before it.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: F(n) = F(n-1) + F(n-2), starting from 0 and 1.
Why this works: the recursion explains the idea, but it repeats work. Each value only needs the two before it, so roll two variables forward.
Example: n = 5
0, 1 → 1 → 2 → 3 → 5F(5) = 5
✦Hints open one at a time
The direct recursion F(n) = F(n−1) + F(n−2) recomputes the same values again and again: O(2^n).
Draw the recursion tree for n = 5 and count how often F(2) appears.
Keep only the last two values and loop.
↗Approach
Understand the recursive definition and its base cases first, then notice each value depends only on the previous two. Roll two variables forward n times.
</>Solution (Java)
class Solution {
public int fib(int n) {
if (n < 2) return n; // base cases F(0)=0, F(1)=1
int prev = 0, cur = 1;
for (int i = 2; i <= n; i++) {
int next = prev + cur;
prev = cur;
cur = next;
}
return cur;
}
}!Common mistake
Missing a base case — the recursion never stops (StackOverflowError).
Complexity
- Time: O(n).
- Space: O(1).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon