======

The `memo`

package implements a simple in-memory cache for the results
of repeated computations.

Consider this terrible way to compute the Fibonnacci sequence:

fib <- function(n) if (n <= 1) 1 else fib(n-1) + fib(n-2)

This function is very slow to compute larger values. Each call to `fib(n)`

with
`n > 1`

generates two more calls to `fib`

, leading to a runtime complexity of
`O(2^n)`

. Let's count how many recursive calls to `fib`

are involved in computing
each `fib(n)`

:

count.calls <- function(f) { force(f) function(...) { count <<- count+1; f(...) } } with_count <- function(f) { force(f) function(x) { count <<- 0 c(n=x, result=f(x), calls=count) } } fib <- count.calls(fib) t(sapply(1:16, with_count(fib)))

The number of calls increases unreasonably. This is because, say, `fib(6)`

calls
both `fib(5)`

and `fib(4)`

, but `fib(5)`

also calls `fib(4)`

, so the second
computation is wasted work, and this gets worse the higher `n`

you have. We
would be in better shape if later invocations of `fib`

could access the values
that were previously computed.

By wrapping `fib`

using `memo`

, fewer calls are made:

library(memo) fib <- memo(fib) t(sapply(1:16, with_count(fib)))

Here is only called to compute new values. Note that `fib(16)`

only took two
calls to compute, because `fib(15)`

was previously computed. To compute `fib(16)`

*de novo* takes 17 calls:

fib <- function(n) if (n <= 1) 1 else fib(n-1) + fib(n-2) fib <- memo(count.calls(fib)) with_count(fib)(16)

**Any scripts or data that you put into this service are public.**

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.