Since the output of a pure function for a given input is always the same, you can cache the function results and avoid a possibly costly recalculation. This process, which implies evaluating an expression only the first time and caching the result for later calls, is called memoization.
We will come back to this idea in Chapter 6, Producing Functions – Higher-Order Functions, but let's look at an example done by hand. The Fibonacci sequence is always used for this example because of its simplicity and its hidden calculation costs. This sequence is defined as follows:
- For n=0, fib(n)=0
- For n=1, fib(n)=1
- For n>1, fib(n)=fib(n-2)+fib(n-1)
Fibonacci's name actually comes from filius Bonacci, or son of Bonacci. He is best known ...
