A cache stores previously computed values so repeated recursive calls can reuse them instead of repeating the same work. section 7.3
In naive Fibonacci recursion, calls such as fib(2) recur repeatedly, producing exponential execution time. Adding an array cache trades storage for computation and reduces execution time to linear in n. section 7.3
Cached Fibonacci
fibCacheRec checks cache[n-1]. If the entry is empty, it computes the value recursively, stores it, and returns the stored result; fibCache initializes the array before the first call. section 7.3
8 size_t gcd2(size_t a, size_t b) {
9 assert(a <= b);
10 if (!a) return b;
11 size_t rem = b % a;
12 return gcd2(rem, a);
13 }
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":1},{\"line\":0,\"ch\":2}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":1,\"ch\":1},{\"line\":1,\"ch\":2}],[{\"line\":1,\"ch\":7},{\"line\":1,\"ch\":13}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":2}],[{\"line\":2,\"ch\":7},{\"line\":2,\"ch\":9}],[{\"line\":2,\"ch\":15},{\"line\":2,\"ch\":21}],[{\"line\":4,\"ch\":7},{\"line\":4,\"ch\":13}],[{\"line\":3,\"ch\":0},{\"line\":3,\"ch\":2}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":4,\"ch\":0},{\"line\":4,\"ch\":2}],[{\"line\":2,\"ch\":15},{\"line\":2,\"ch\":21}],[{\"line\":4,\"ch\":7},{\"line\":4,\"ch\":13}],[{\"line\":5,\"ch\":0},{\"line\":5,\"ch\":2}]]"}
!@%STYLE%@!
The complete cached-Fibonacci implementation shows the cache array, initialization, recursive lookup, and assignment steps. section 7.3
