> As, we can see the optimal cache size of fib function is 5. Increasing cache size will not result in much gain in terms of speedup.
Try it with fib(35), curious what you find.
Try it with fib(35), curious what you find.
Why 3 is optimal, because of how recursion and LRU work. I wish i can explain it using animation.
You can play with it. https://repl.it/repls/NocturnalIroncladBytecode#main.py
If this theory is correct, every recursive function f(n) requiring access to f(n-x) should have x+1 as maximum usefull cache size.
Because of the way the recursion goes down the tree depth-first, I think 5 basically cuts down the computation to fib(10-5) = fib(5) which is pretty manageable, so the author couldn't really see any further measurable performance gains by increasing the cache further. I think for fib(35) it'd be clear that cache size 35 would help compared to cache size 5. (I picked 35 instead of, say, 300, because I think 300 would just not finish with cache size 5, it'd take forever haha.)