Understanding a memoized Fibonacci function

user_15236699 0
Viewed 645

The function, taken from here:

function fib(n,memo) {
   memo = memo || {}
   if (memo[n]) {
      return memo[n]
   }
   if (n <= 1) {
      return 1
   }
   return memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
}

This is a working memoized recursive function that takes parameter n and returns the n:th Fibonacci number.

What I fail to grasp is that how can the memo object with assigned values be visible across different recursive function calls? Here's a picture that I assume to be a correct depiction of what happens when the function is called with parameter 4, but please correct me if it's not:

Recursion chart

Take a note of the function calls marked with 1. and 2. and their respective comments in the picture. How is it that number 2 (fib(1)) gets supplied a memo parameter that contains the value assigned in number 1 (fib(2))? Shouldn't the memo supplied to number 2 (fib(1)) be the same that was supplied to the fib(3) call above it, which would be an empty object?

I know that the memo object could just be a global variable and all assignments to it would automatically be visible in all the recursions, but I'm just trying wrap my head around how this particular technique works.

Hopefully this description made sense. Thank you.

memoization fibonacci recursion javascript
1 Answers

Intro: why does this work?

You said in the comments that the pass-by-value description helped clarify this. But the basic point is that in the recursive calls the cache is passed to them from the outside. They get a copy of the reference to a shared value. The initial call accepts a cache, and if it's not supplied, creates a new one.

If you wanted, you could call it like this:

const fibCache = {};

fib (5, fibCache) //=> 8

fib (7, fibCache) //=> 21

and you wouldn't recalculate the values of fib (2), fib (3), fib (4), or fib (5) in the second call. But it's annoying to have to keep that around. Below we create a helper function that lets us create memoized functions with permanent caches.

Memoization Strategies

This is what might be thought of as an lower level of memoization. The function is memoized, but only for the length of the initial call and all the recursive calls it generates. There are ways to memoize functions so that the cache lasts between calls.

If we start with a non-memoized version like this:

function fib1 (n) {
  if (n <= 1) {
    return 1
  }
  console .log (`Calculating fib1 (${n})`)
  return fib1 (n - 1) + fib1 (n - 2)
}

console .log (`fib1 (5) returns ${fib1 (5)}`)
console .log ('------')
console .log (`fib1 (5) returns ${fib1 (5)}`)

We will get output like this:

Calculating fib1 (5)
Calculating fib1 (4)
Calculating fib1 (3)
Calculating fib1 (2)
Calculating fib1 (2)
Calculating fib1 (3)
Calculating fib1 (2)
fib1 (5) returns 8
------
Calculating fib1 (5)
Calculating fib1 (4)
Calculating fib1 (3)
Calculating fib1 (2)
Calculating fib1 (2)
Calculating fib1 (3)
Calculating fib1 (2)
fib1 (5) returns 8

Obviously that will run into problems when we try larger values.

Using the version you supplied:

function fib2 (n,memo) {
   memo = memo || {}
   if (memo[n]) {
      return memo[n]
   }
   if (n <= 1) {
      return 1
   }
   console .log (`Calculating fib2 (${n})`)
   return memo[n] = fib2 (n - 1, memo) + fib2 (n - 2, memo)
}

console .log (`fib2 (5) returns ${fib2 (5)}`)
console .log ('------')
console .log (`fib2 (5) returns ${fib2 (5)}`)

We reduce this so that the internal calls are no longer repeated, but between external calls, we still repeat:

Calculating fib2 (5)
Calculating fib2 (4)
Calculating fib2 (3)
Calculating fib2 (2)
fib2 (5) returns 8
------
Calculating fib2 (5)
Calculating fib2 (4)
Calculating fib2 (3)
Calculating fib2 (2)
fib2 (5) returns 8

If we can store the cache somewhere external to the function call, we can make a version that doesn't repeat at all:

const memoize = (fn) => {
  const cache = {}
  return function (x) {
    if (!(x in cache)) {
      cache [x] = fn (x)
    }
    return cache [x]
  }
}

const fib3 = memoize (function (n) {
  if (n <= 1) {
    return 1
  }
  console .log (`Calculating fib3 (${n})`)
  return fib3 (n - 1) + fib3 (n - 2)
})

console .log (`fib3 (5) returns ${fib3 (5)}`)
console .log ('------')
console .log (`fib3 (5) returns ${fib3 (5)}`)

Calculating fib3 (5)
Calculating fib3 (4)
Calculating fib3 (3)
Calculating fib3 (2)
fib3 (5) returns 8
------
fib3 (5) returns 8

Here we store the cache in a closure generated by the call to a memoize helper. For many problems this is a much more satisfactory version. This works also for those cases when there's no recursion but the calculations are time-consuming.

user_12436410
Related