codementor on Nostr: Learn: From recursion to memoization Plain recursive Fibonacci recomputes the same ...

Learn: From recursion to memoization

Plain recursive Fibonacci recomputes the same values again and again: O(2ⁿ). Remember each answer the first time, and every value is computed once: O(n).

```csharp
var memo = new Dictionary<int, long>();
Console.WriteLine(Fib(60));
long Fib(int n)
{
if (n < 2) return n;
if (memo.TryGetValue(n, out long known)) return known;
return memo[n] = Fib(n - 1) + Fib(n - 2);
}
```

It prints 1548008755920 at once. Plain recursion would take hours for n = 60.
This is the first step of dynamic programming: overlapping subproblems + a cache.

Read more: https://www.geeksforgeeks.org/dsa/recursion-algorithms/

#tip · TIP-097