Memoization

memoize <- function(f) {
  memo <- new.env()
  function(x) {
    key <- as.character(x)
    if (!exists(key, memo, inherits = FALSE)) {
      memo[[key]] <- f(x)
    }
    memo[[key]]
  }
}

# Counts every call of fibonacci
counts <- new.env()
counts$calls <- 0

fibonacci <- function(x) {
  counts$calls <- counts$calls + 1
  if (x <= 1) return(x)
  fibonacci(x - 1) + fibonacci(x - 2)
}

mem_fibonacci <- memoize(fibonacci)

f20 <- mem_fibonacci(20)
# f20 = 6765
calls_first <- counts$calls
# calls_first = 21891

# Cached: fibonacci is not called again
f20_again <- mem_fibonacci(20)
# f20_again = 6765
calls_second <- counts$calls
# calls_second = 21891

# Only the outer call is cached
f21 <- mem_fibonacci(21)
# f21 = 10946
calls_third <- counts$calls
# calls_third = 57312

cat("f20 =", f20, "\n")
cat("calls_first =", calls_first, "\n")
cat("f20_again =", f20_again, "\n")
cat("calls_second =", calls_second, "\n")
cat("f21 =", f21, "\n")
cat("calls_third =", calls_third, "\n")