# memo

======

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

## Fibonnacci example

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)
```

## Try the memo package in your browser

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

memo documentation built on May 2, 2019, 7:01 a.m.