Recursion With Memoization

(Textbook: Section 16.4)

How Do WE Find Fibonacci Numbers?

We don’t start from scratch.

We “look up” the two previous Fibonacci numbers, when we need to find a new one:

• first two numbers are 1 and 1, so …
• third is second plus first so \(1+2=2\);
• fourth is third plus second, so \(2+1=3\),
• etc.

New Approach: A Memo-Sheet

fib_mem_factory <- function() {
  ## the memo-sheet:
  memo <- list()
  function(n) {
    # names of list-elements are strings:
    key <- as.character(n)
    if (!is.null(memo[[key]])) {
      # woo-hoo, we hit the memo-sheet!
      return(memo[[key]])
    }
    if (n %in% c(1, 2)) {
      # we are at a base case, so add this info to the memo sheet:
      memo[[key]] <<- 1
      return(1)
    }
    new_fib <- Recall(n - 2) + Recall(n - 1)
    # record the result in the memo sheet:
    memo[[key]] <<- new_fib
    # return the result:
    new_fib
  }
}

Make a Fib Function

fib_better <- fib_mem_factory()

Try iy out:

Much faster!

Why So Much Faster?

fib_mem_factory_count <- function() {
   ## the memo-sheet:
  memo <- list()
  function(n) {
    # update a counter:
    counter <<- counter + 1
    key <- as.character(n)
    if (!is.null(memo[[key]])) {
      return(memo[[key]])
    }
    if (n %in% c(1, 2)) {
      memo[[key]] <<- 1
      return(1)
    }
    new_fib <- Recall(n - 2) + Recall(n - 1)
    memo[[key]] <<- new_fib
    new_fib
  }
}

Try It

Because we use the memo sheet so much, we need far fewer recalls.

An Illustrative App

To see the memo at work interactively, consult this app.

Using local()

We could also use local() to create a memo-using function:

another_fast_fib <- local({
  memo <- list()
  function(n) {
    key <- as.character(n)
    if (!is.null(memo[[key]])) {
      return(memo[[key]])
    }
    if (n %in% c(1, 2)) {
      memo[[key]] <<- 1
      return(1)
    }
    new_fib <- Recall(n - 2) + Recall(n - 1)
    memo[[key]] <<- new_fib
    new_fib
  }
})

Try It Out