JuniorCodeVery commonNot answered yet
Compute Fibonacci numbers (iterative, recursive, memoised)
Return the n-th Fibonacci number, with fib(0) = 0, fib(1) = 1.
Requirements:
not the O(2ⁿ) naive recursion.
- O(n) time and O(1) space — bottom-up iteration with two rolling variables,
- Get the base cases right (
fib(0)=0,fib(1)=1,fib(2)=1). - Use
uint64_tfor the result; notefib(93)is the last value that fits.
uint64_t fib(int n) {
// your code here
}Write the implementation.
Naive recursion is O(2ⁿ) — catastrophically slow. Bottom-up iteration uses two variables and runs in O(n) time and O(1) space. Top-down memoisation (cache of results) is also O(n) but O(n) space. Matrix exponentiation achieves O(log n).
- ✗Writing naive recursion without memoisation — fib(40) already takes seconds
- ✗Overflow for large n — use
uint64_tor__int128explicitly and note that fib(93) is the last value fitting uint64_t - ✗Off-by-one in the base case: fib(0)=0, fib(1)=1, fib(2)=1
- →How does matrix exponentiation compute Fibonacci in O(log n)?
- →How would you compute fib(n) mod M for very large n?
Contents
Task
Implement Fibonacci in three ways: naive recursion, memoisation, iterative.
Solution
// Iterative — O(n) time, O(1) space (preferred)
uint64_t fibIter(int n) {
if (n <= 1) return n;
uint64_t a = 0, b = 1;
for (int i = 2; i <= n; ++i) { uint64_t c = a + b; a = b; b = c; }
return b;
}Key points
- Naive recursion is O(2ⁿ) — only use it to illustrate memoisation.
- Iterative with two variables: O(n) time, O(1) space — preferred in practice.
fib(93)is the last value that fits inuint64_t.
Contents
