How it works
Naive recursive Fibonacci calculation repeats the same subproblems many times. Memoization stores a result after computing it, so later calls for the same argument can reuse it. The cache starts with the two base cases and fills only the missing values needed to answer Fib(20).
The computed counter increments on a cache miss after the lookup. Values two through twenty are the nineteen new subproblems, so the first call prints nineteen. The second call returns the cached result immediately and leaves the counter unchanged. This makes the avoided work visible without relying on a noisy stopwatch measurement.
The cache key must include every input that influences the result. Fibonacci depends only on n in this example. A real calculation depending on a mode, locale, or version would need those facts represented in its key or in a carefully bounded cache lifetime. Otherwise memoization could reuse a result from the wrong context.
Caching also consumes memory and can extend the lifetime of data. This lesson uses a small local dictionary whose owner is clear. An unbounded global cache for arbitrary user input can grow indefinitely. Decide when entries expire or when the whole cache is discarded instead of treating reuse as free.
Practice by requesting Fib(10) before Fib(20) and predicting the total number of distinct computed values. Then request Fib(21) and explain why only one new subproblem must be computed. Include negative input and a sufficiently large value to observe the checked arithmetic boundary.
Finally, compare this top-down version with a bottom-up loop that keeps only the previous two results. Both avoid repeated recursive work, but they have different storage and call-stack behavior. Choose according to whether the surrounding task benefits from retaining many query results or only needs one final value.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
var cache = new Dictionary<int, long> { [0] = 0, [1] = 1 };
int computed = 0;
Console.WriteLine(Fib(20));
Console.WriteLine(computed);
Console.WriteLine(Fib(20));
Console.WriteLine(computed);
long Fib(int n) {
if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
if (cache.TryGetValue(n, out long known)) return known;
computed++;
long value = checked(Fib(n - 1) + Fib(n - 2));
cache[n] = value;
return value;
}
Expected output
6765 19 6765 19
Count cache misses, not all calls, when demonstrating computed subproblems.