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 re-calculation. 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 see an example done by hand. The Fibonacci sequence is always used for examples, 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 ...