The Fibonacci sequence begins with F₁ = 1 and F₂ = 1; each later term is the sum of the preceding two: Fᵢ = Fᵢ₋₁ + Fᵢ₋₂ for i > 2. section 7.3
A direct recursive C implementation
size_t fib(size_t n) { if (n < 3) return 1; return fib(n - 1) + fib(n - 2); } The base case returns 1 for the first two positions. Otherwise, the function recursively computes and adds the two preceding values. section 7.3
The sequence grows exponentially: Fₙ is approximately φⁿ/√5, where φ = (1 + √5)/2. The direct recursive function consequently repeats work and has exponential execution time. section 7.3
Recursive implementations can avoid repeated computation in two ways:
- Cache previously computed values; the resulting computation takes time proportional to n. section 7.3
- Keep only the latest two values in a two-element buffer while recursing. section 7.3
size_t fib(size_t n) [[__unsequenced__]] {
if (n < 3)
return 1;
else
return fib(n-1) + fib(n-2);
}
Inspect the compact recursive implementation and its base case. section 7.3
