How is the Fibonacci sequence defined
The Fibonacci sequence is a sequence of integers in which each number is the sum of the two preceding numbers. Conventionally, F(0) = 0 and F(1) = 1, producing 0, 1, 1, 2, 3, 5, 8, 13, 21, ….
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Definition and Recurrence
-
Recurrence relation:
F(n) = F(n - 1) + F(n - 2)forn ≥ 2 -
Base cases:
F(0) = 0,F(1) = 1 -
Closed form (Binet’s formula):
F(n) = (φⁿ - ψⁿ) / √5, whereφ = (1 + √5) / 2 ≈ 1.618andψ = (1 - √5) / 2 ≈ -0.618 -
Binet’s formula loses precision for large
nwhen evaluated with floating-point arithmetic and can eventually overflow. Python’s arbitrary-precision integers avoid overflow, but a floating-point implementation of the formula is still inexact.
Mathematical Properties
-
Growth rate:
F(n) ≈ φⁿ / √5, so the sequence grows exponentially with baseφ, the golden ratio. -
Divisibility: For positive
m ≥ 3,F(m)dividesF(n)if and only ifmdividesn. The casem = 2is exceptional becauseF(2) = 1divides every Fibonacci number. -
Cassini’s identity:
F(n - 1) · F(n + 1) - F(n)² = (-1)ⁿ -
Partial sum:
F(0) + F(1) + … + F(n) = F(n + 2) - 1
Computational Approaches
| Approach | Time Complexity | Space Complexity | When to Use |
|---|---|---|---|
| Naive recursion | O(φⁿ), approximately O(1.618ⁿ) |
O(n) stack |
Teaching only; exponential because of overlapping subproblems |
| Memoization (top-down DP) | O(n) |
O(n) cache plus O(n) stack |
When recursion is natural and the recursion depth is safe |
| Iterative (bottom-up DP) | O(n) |
O(1) |
Simple general-purpose solution when linear time is sufficient |
| Fast doubling or matrix exponentiation | O(log n) |
O(log n) stack recursively or O(1) iteratively |
Large indices requiring logarithmically many arithmetic operations |
Why fast doubling is O(log n): It uses the identities
F(2k) = F(k) · [2 · F(k + 1) - F(k)]
F(2k + 1) = F(k + 1)² + F(k)²
to halve the index at each step, analogous to exponentiation by squaring.
Complexity Details
-
Naive recursion: Time is
O(φⁿ)because the recursive call tree grows exponentially. Space isO(n)for the recursion stack. -
Memoization: Each
F(i)is computed once, givingO(n)time andO(n)total auxiliary space for the cache and recursion stack. -
Iterative: One loop and two stored Fibonacci values give
O(n)time andO(1)auxiliary space. -
Fast doubling: The recursion depth is
O(log n), so time isO(log n)and recursive stack space isO(log n); an iterative version usesO(1)auxiliary space.
All space figures exclude the input integer and include recursive call stacks. These time and space bounds use the standard unit-cost arithmetic model; with arbitrary-precision integers, runtime and memory also depend on the resulting integers’ Θ(n) bit lengths.
Integer Size Considerations
-
Python 3’s
inthas arbitrary precision, so Fibonacci values do not overflow, subject to available memory. -
A signed 64-bit integer has a maximum of
9,223,372,036,854,775,807, andF(93) = 12,200,160,415,121,876,738exceeds it. -
Use an appropriate wider or arbitrary-precision type for larger values:
__int128where supported in C++,BigIntegerin Java, orBigIntin JavaScript. Modular arithmetic is another option when onlyF(n) mod mis required.
Common Pitfalls and Interview Tips
-
Off-by-one errors: Confirm whether the problem uses
F(0) = 0, F(1) = 1orF(1) = 1, F(2) = 1. -
Recursion depth: Python 3.12’s default recursion limit is approximately
1,000, so naive and memoized recursive implementations can fail near that depth. Prefer an iterative implementation or raise the limit cautiously. -
Mutating input: Avoid modifying caller-owned data unless the problem explicitly requires it.
-
Memoization purpose: Fibonacci is the classic example of overlapping subproblems: naive recursion recalculates the same Fibonacci values repeatedly.
-
Follow-up questions:
-
Compute
F(n) mod musing fast doubling with modular arithmetic. -
Find the index of a given Fibonacci number using an estimate followed by verification, or binary search with a Fibonacci lookup function.
-
Sum even Fibonacci numbers using the fact that
F(3k)is even. -
Optimize
O(n)dynamic-programming space toO(1)by retaining only the last two values.