Quick answer
Prefer O(n) iteration with BigInt for large n. Memoized recursion teaches the tree but uses more memory.
Formula
- Base cases F(0), F(1)
- a,b = b, a+b in a loop
Introduction
Fibonacci in programming is a rite of passage and a performance lesson. The naive recursive function is short to type but expensive to run.
Production code, and our public calculator, use iteration with integer types that do not overflow silently.
Read formula versus recursive method for complexity tables before you ship homework repos.
Pair this guide with how the public Fibonacci calculator works to test your function outputs.
Sections cover algorithms, dynamic programming, time complexity, and language notes.
Algorithms you should recognize
Naive recursion: define fib(n) as fib(n-1)+fib(n-2) with bases. Exponential time without memo.
Top-down DP: cache results in an array or map. Linear time, linear memory.
Bottom-up iteration: two variables rolling forward. Linear time, constant memory.
Matrix exponentiation: advanced O(log n) time for huge n in competitive programming.
JavaScript and Python notes
- JavaScript: use BigInt for n>70 in Number
- Python: ints are arbitrary precision
Match indexing with your test cases. Unit tests should assert fib(0)==0 and fib(1)==1 if that is your contract.
Property-based tests can compare fib(n) against the home site for random n under 500.
Manual math steps on paper use the same recurrence your function should implement in code.
Tables for expected values are handy fixtures when you write unit tests for fib(10), fib(15), and fib(20).
Implementation checklist
- Define contract Document indexing in the function docstring.
- Choose algorithm Default to iteration unless teaching recursion.
- Add tests Include n=0, n=1, and n=20 at minimum.
- Compare to site Open the home calculator for disputed n.
Test case table
fib(10) should return 55. fib(15) should return 610. fib(20) should return 6765.
If any fail, check off-by-one loops that start at 1 instead of 0.
Log intermediate a and b in the loop when debugging student submissions.