Caching retains previously computed values so recursive calls can reuse them instead of repeating the same computation. It trades storage for computation time. section 7.3
Caching Fibonacci results
The naive recursive fib function recomputes calls such as fib(2), producing exponential execution time. fibCacheRec stores each computed Fibonacci value in an array and computes it only when the corresponding cache entry is empty, reducing execution time to linear in n. section 7.3
/* Compute Fibonacci number n with the help of a cache that may
hold previously computed values. */
size_t fibCacheRec(size_t n, size_t cache[static n]) {
if (!cache[n-1]) {
cache[n-1]
= fibCacheRec(n-1, cache) + fibCacheRec(n-2, cache);
}
return cache[n-1];
}
size_t fibCache(size_t n) {
if (n+1 <= 3) return 1;
/* Set up a VLA to cache the values. */
#if __STDC_VERSION__ > 202311L
/* Since C23, VLA can be default initialized. */
size_t cache[n] = { };
#else
size_t cache[n]; memset(cache, 0, n*sizeof(*cache));
#endif
/* Non-trivial initialization is replaced by assignment. */
cache[0] = 1; cache[1] = 1;
/* Call the recursive function. */
return fibCacheRec(n, cache);
}
Inspect the complete C implementation, including cache setup, base values, recursive lookup, and C23-versus-pre-C23 VLA initialization. section 7.3
TAKEAWAY
- Improve the algorithm before relying on implementation cleverness: changing exponential recursion to cached recursion can dramatically improve performance. section 7.3
