Memoizing recursive functions

A memoized function, avoids recomputing previous results by looking them up in a table (this only makes sense for functions without side-effects).

Memoizing recursive functions can be a bit tricky, let’s take the exponential fibonacci function as an example:

function fib(x) {
  if (x < 2)
     return x
  else
     return fib(x-2) + fib(x-1)
}
 
print(fib(100)) // this will time out !

we add a table to fibmem to cache the results of fib (note that fib references fibmem in the recursive call, no memoization would take place otherwise).

function fib(x) {
  if (x < 2)
     return x
  else
     return fibmem(x-2) + fibmem(x-1)
}
 
var cache = {}
function fibmem(x) {
  if (x in cache)
     return cache[x]
  else {
     var res = fib(x)
     cache[x] = res   
     return res
  }
}
 
print(fibmem(100))

All is well, but what about writing a function doing the memoization for us (we’ll just consider one-argument functions here) ?

Here’s a first attempt, given a function f, we return a new function that holds a reference to a lookup table and to the function f when we need to compute a result for the first time

function fib(x) {
  if (x < 2)
     return x
  else
     return fib(x-2) + fib(x-1)
}
 
function memoize(f) {
  var cache = {}
  return function(x) {
    if (x in cache)
       return cache[x]
    else {
       var res = f(x)
       cache[x] = res   
       return res
    }
  }
}
 
var fibm = memoize(fib)
print(fibm(100)) // this will time out

Uh oh!
The call to f, on line 14, escapes out of the memoized function, never to return. No memoization occurs.

How can we make f reference its memoized-self (like we did with fib and fibmem above) ?
By assigning the memoized function to the fib identifier !

function fib(x) {
  if (x < 2)
     return x
  else
     return fib(x-2) + fib(x-1)
}
 
function memoize(f) {
  var cache = {}
  return function(x) {
    if (x in cache)
       return cache[x]
    else {
       var res = f(x)
       cache[x] = res   
       return res
    }
  }
}
 
fib = memoize(fib)
print(fib(100))

Let’s recap:

1) A recursive function references itself with a name, here the name fib points to the fibonacci routine.

2) The memoize function returns another function that captures the name of the routine to be memoized (and the name of the lookup table).

3) When we call memoize over fib, the name captured references the unmemoized fibonacci routine.

4) When we assign memoize(fib) to fib, we make the captured fib name point to the memoized function.

Applying the memoized fibonacci function to a number results in a series of mutually recursive calls between the original (now nameless) fibonacci routine and the memoized routine.

Now if you want to read about a really fancy way to achieve the same results, check this article about a memoizing Y combinator.

Ce contenu a été publié dans Uncategorized par . Mettez-le en favori avec son permalien.

Les commentaires sont fermés.