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: Lookup Table

fib_mem_factory <- function(verbose = FALSE) {
  ## the memo sheet:
  known_fibs <- numeric()
  ## for verbose option, to count call of fib-function:
  counter <- 0
  function(n) {
    counter <<- counter + 1
    if (verbose) cat("this is call ", counter, "\n", sep = "")
    if (n <= length(known_fibs) & !is.na(known_fibs[n])) {
      if (verbose) cat("we already know this one!\n")
      return(known_fibs[n])
    }
    if (n %in% c(1, 2)) {
      if (verbose) cat("got to a base fib-value\n")
      known_fibs[n] <<- 1
      return(1)
    }
    if (verbose) cat("finding fib", n-2, "\n")
    fibp <- Recall(n - 2)
    if (verbose) cat("finding fib ", n-1, "\n")
    fibpp <- Recall(n - 1)
    new_fib <- fibp + fibpp
    known_fibs[n] <<- new_fib
    new_fib
  }
}

Make a Fib Function

fib_better <- fib_mem_factory(verbose = FALSE)

fib_better(30)

[1] 832040

fib_better(50)

[1] 12586269025

Much faster!

Why So Much Faster?

fib_better_2 <- fib_mem_factory(verbose = TRUE)
fib_better_2(10)

this is call 1
finding fib 8 
this is call 2
finding fib 6 
this is call 3
finding fib 4 
this is call 4
finding fib 2 
this is call 5
got to a base fib-value
finding fib  3 
this is call 6
finding fib 1 
this is call 7
got to a base fib-value
finding fib  2 
this is call 8
we already know this one!
finding fib  5 
this is call 9
finding fib 3 
this is call 10
we already know this one!
finding fib  4 
this is call 11
we already know this one!
finding fib  7 
this is call 12
finding fib 5 
this is call 13
we already know this one!
finding fib  6 
this is call 14
we already know this one!
finding fib  9 
this is call 15
finding fib 7 
this is call 16
we already know this one!
finding fib  8 
this is call 17
we already know this one!

[1] 55