Why are these memoised functions different?

Question

I see that if I use memoise for a function in two different ways, I get two different behaviors, and I would 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 very fast because it reuses recursive results, while strategy 2 only runs quickly if the exact entry was noticed earlier.

Can someone explain to me why this is?

Answer 1

I think the reason is simple. In the slow case, the fib_not_as_fast function fib_not_as_fast remembered. Inside the function, fib is called, which is not stored in memory. To be more detailed: when calculating fib_not_so_fast(24) inside the function, you have fib(22) + fib(23) . Both were not seen.

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