The Fibonacci sequence begins 0, 1, 1, 2, 3, 5, 8, …; each later term is the sum of the preceding two. With zero-based indexing, fib(0) is 0 and fib(1) is 1. section 1.1
Small Swift implementations expose the main design choices:
- A direct recursive translation needs base cases; without them, unsigned subtraction leads to infinite recursion. section 1.1
- The base cases n < 2 return n, while larger inputs split into fib(n - 2) and fib(n - 1). section 1.1
- Memoization stores computed values in a dictionary, avoiding repeated recursive work. section 1.1
- An iterative version tracks the previous two values and updates them in a loop. section 1.1
Tracing fib(4)
The recursive call fib(4) branches into fib(3) and fib(2), and those branches repeatedly revisit fib(2), fib(1), and fib(0). The trace makes duplicated computation visible. section 1.1
0, 1, 1, 2, 3, 5, 8, 13, 21...
Use the compact sequence as a quick reference for the values produced by the recurrence. section 1.1
