why are these memoised functions different?

Question

I see that if I use memoise on a function in two different ways, I get two different behaviours, and I'd like to understand why.

# Non Memoised function
fib <- function(n) {
  if (n < 2) return(1)
  fib(n - 2) + fib(n - 1)
}

system.time(fib(23))
system.time(fib(24))

library(memoise)

# Memoisation stragagy 1
fib_fast <- memoise(function(n) {
  if (n < 2) return(1)
  fib_fast(n - 2) + fib_fast(n - 1)
})

system.time(fib_fast(23))
system.time(fib_fast(24))

# Memoisation strategy 2
fib_not_as_fast <- memoise(fib)

system.time(fib_not_as_fast(23))
system.time(fib_not_as_fast(24))

Strategy 1, is really fast, as it reuses the recursive results, whereas stratagy 2 is only fast if the exact input has been seen before.

Can someone explain to me why this is?

Answer 1

I think that the reason is simple. In the slow case, the function fib_not_as_fast is memoised. Inside the function, fib is called, which is not memoised. To be more detailed: when you calculate fib_not_so_fast(24), inside the function you have fib(22) + fib(23). Both of these have not been memoised.

In fib_fast, however, you use the memoised version also in the recursion. So, in this case, fib_fast(24) needs to evaluate fib_fast(22) + fib_fast(23). Both these function calls have already happened, when you calculated fib_fast(23) and are thus memoised.

What does work is to memoise a function later, after it has been defined. So, simply redefining the function fib() as fib <- memoise(fib) will work.