Recursion With Memoization

(Textbook: ——)

Problems with Fibonacci Function

Recall the Fibonacci Function

fib <- function(n) {
  ## Base cases:
  if (n %in% c(1, 2)) {
    return(1)
  }
  ## Recursive case:
  Recall(n - 1) + Recall(n - 2)
}

fib(10)

[1] 55

Seems to work just fine.

But …

Try:

fib(30)

Takes a scary long time to finish.

Don’t even bother with:

fib(50)

Diagnosis

The number of recalls that fib() must make grows exponentially with the size of n.

Let’s investigate this:

counter <- 0
fib2 <- function(n) {
  counter <<- counter + 1
  if (n %in% c(1, 2)) {
    return(1)
  }
  Recall(n - 1) + Recall(n - 2)
}
fib2(10)

[1] 55

counter

[1] 109

Further Investigation

## highest fib number to find:
m <- 25
## set up some results vectors:
calls <- numeric(m)
fibs <- numeric(m)
for (i in 1:m) {
  counter <- 0
  fibs[i] <- fib2(i)
  calls[i] <- counter
}

calls - (fibs + fibs - 1)

 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Math Fact: the number of calls made by the fib() function when finding the nth Fibonacci number is:

\[2 \times F_n - 1.\]

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.

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