Fibonacci in python should use lru_cache

[ashwinvis]

This code:

https://github.com/JuliaLang/Microbenchmarks/blob/d97a03050052faf22308cfdb60c8066431b6e6da/perf.py#L11-L16

is a textbook use-case for lru_cache and is even mentioned in the documentation (https://docs.python.org/3/library/functools.html?highlight=lru_cache#functools.lru_cache). In my laptop, the timings went from 2.31623 to 0.00047 seconds after that change.

[johnfgibson]

This benchmark is meant as a test of recursion, not the best way to calculate Fibonacci numbers.

From https://julialang.org/benchmarks/

It is important to note that the benchmark codes are not written for absolute maximal performance (the fastest code to compute recursion_fibonacci(20) is the constant literal 6765). Instead, the benchmarks are written to test the performance of identical algorithms and code patterns implemented in each language. For example, the Fibonacci benchmarks all use the same (inefficient) doubly-recursive algorithm, and the pi summation benchmarks use the same for-loop.

[ashwinvis]

I see your point. If those are the rules of this microbenchmarks then so be it.

FWIW, lru_cache is in the Python standard library, and is the standard way to write recursive functions, where the input arguments are hashable - not limited to this particular case of Fibonacci. The algorithm is the same... it is just an optimization. I felt this should be mentioned for people who look at these results.