Memoized, Recursive Factorial Function

Memoized, recursive factorial function?

Well the neatest way I can think of to do this in C++ is probably using a function object to store the memoized values. I guess this is probably slightly similar to your python decorator, although I have never really done any python. The code would look something like this:

template <typename T, T (*calc)(T)>
class mem {
  std::map<T,T> mem_map;

public:
  T operator()(T input) {
    typename std::map<T,T>::iterator it;

    it = mem_map.find(input);
    if (it != mem_map.end()) {
      return it->second;
    } else {
      T output = calc(input);
      mem_map[input] = output;
      return output;
    }
  }
};

The code defines a template class that takes in a typename and a function pointer, the function operator is then defined on the class allowing it to be called. The function operator takes in an input value checks if said value is in a map, then either simply returns it from the map or calculates it (using the function pointer), adds it to the map and then returns it.

So assuming you define some processing function like say:

int unity(int in) { return in; }

You would use the code like this:

mem<int, unity> mem_unity;
int y;
y = mem_unity(10);

So we define an instance of the mem class which takes our value type and processing function as template parameters, then simply call this class as a function.

Javascript factorial function memoization

You don't buy much from memoizing this since you only use each value once. After you've called the function you do have the cache for a second call, but we often think of memoizing as something that happens in a cache that only exists during the function. For something like that, calculating Fibonacci numbers is a classic example where memoizing is a huge improvement over the naive recursive function.

Having said that, in your function it's not clear why you are using an object for your cache and then searching it. You can just use an array where the indexes will be the number you're looking for calculate. You don't need to search it, just start with the number and recursively call the next lower one. If there's a cache it, it will return. For example:

let cache = [1];function factMemoize(key) {    if (!cache[key]) {      cache[key] = key * factMemoize(key - 1)    } else { // just to demo cache:        console.log("cache hit:", key)    }    return cache[key]}
// only hits cache at the end console.log("6! = ", factMemoize(6))
// second call benefits from cache:console.log("8! = ", factMemoize(8))

Recursive Factorial Function in F# with Memoization

Addressing the comments:

A more common version of the true match would be

|true,result -> result 

you need the bit after the -> to actually return a value.

In the false match, you need to actually compute the factorial, by calculating

n * factorial(n-1)

In fact, a better version of the false case would be

 |false, _ -> 
     let r = n * factorial(n-1)
     factorials.Add(n,r)
     r

Java Memoization of Recursive method

The issue is that your Factorial function does not call recursively into the memoized version of the function.

To fix this, there are a few options.

1. You could parameterize your Factorial function and give it reference to the Function it should call recursively. In the unmemoized case, this will be the function itself; in the memoized case, this will be the memoizing wrapper.

2. You could implement memoization through extending the Factorial function class, overriding, rather than delegating to, the unmemoized apply(). This is difficult to do ad-hoc, but there are utilities out there to create subclasses dynamically (this is a common way of implementing AOP, for example).

3. You could give the base function full knowledge of the memoization to start with.

Here's the gist of the first option:

interface MemoizableFunction<I, O> extends Function<I, O> {

    //in apply, always recurse to the "recursive Function"
    O apply(I input);

    setRecursiveFunction(Function<? super I, ? extends O>);
}

final MemoizableFunction<Integer, Integer> fact = new MemoizableFunction<Integer, Integer>() {

  private Function<Integer, Integer> recursiveFunction = this;

  @Override
  public Integer apply(final Integer input) {
    System.out.println("Fact: " + input);
    if(input == 1)
        return 1;
    else return input * recursiveFunction.apply(input -1);
  }

  //...
};

Factorial Memoization in R

First of all, if you need an efficient implementation, use R's factorial function. Don't write it yourself. Then, the factorial is a good exercise for understanding recursion:

myfactorial <- function(n) {
  if (n == 1) return(1)
  n * myfactorial(n-1)
}

myfactorial(10)
#[1] 3628800

With this function memoization is only useful, if you intend to use the function repeatedly. You can implement memoization in R using closures. Hadley explains these in his book.

createMemFactorial <- function() {
  res <- 1
  memFactorial <- function(n) {
    if (n == 1) return(1)

    #grow res if necessary
    if (length(res) < n) res <<- `length<-`(res, n)

    #return pre-calculated value
    if (!is.na(res[n])) return(res[n])

    #calculate new values
    res[n] <<- n * factorial(n-1)
    res[n]
  }
  memFactorial
}
memFactorial <- createMemFactorial()

memFactorial(10)
#[1] 3628800

Is it actually faster?

library(microbenchmark)
microbenchmark(factorial(10),
               myfactorial(10), 
               memFactorial(10))
#Unit: nanoseconds
#             expr  min     lq    mean median     uq   max neval cld
#    factorial(10)  235  264.0  348.02  304.5  378.5  2463   100 a  
#  myfactorial(10) 4799 5279.5 6491.94 5629.0 6044.5 15955   100   c
# memFactorial(10)  950 1025.0 1344.51 1134.5 1292.0  7942   100  b 

Note that microbenchmark evaluates the functions (by default) 100 times. Since we have stored the value for n = 10 when testing the memFactorial, we time only the if conditions and the lookup here. As you can also see, R's implementation, which is mostly written in C, is faster.

A better (and easier) example implements Fibonacci numbers. Here the algorithm itself benefits from memoization.

#naive recursive implementation
fib <- function(n)  {
  if(n == 1 || n == 2) return(1)
  fib(n-1) + fib(n-2)
}

#with memoization
fibm <- function(n)  {
  if(n == 1 || n == 2) return(1)

  seq <- integer(n)
  seq[1:2] <- 1

  calc <- function(n) {
    if (seq[n] != 0) return(seq[n])
    seq[n] <<- calc(n-1) + calc(n-2)
    seq[n]
  }

  calc(n)
}

#try it:
fib(20)
#[1] 6765
fibm(20)
#[1] 6765

#Is memoization faster?
microbenchmark(fib(20),
               fibm(20))
#Unit: microseconds
#     expr      min       lq       mean    median        uq       max neval cld
# fib(20)  8005.314 8804.130 9758.75325 9301.6210 9798.8500 46867.182   100   b
#fibm(20)    38.991   44.798   54.12626   53.6725   60.4035    97.089   100  a 

How do I generate memoized recursive functions in Clojure?

This seems to work:

(defn make-fibo [y]
  (with-local-vars
      [fib (memoize
            (fn [x]
              (if (< x 2)
                y
                (+ (fib (- x 2)) (fib (dec x))))))]
    (.bindRoot fib @fib)
    @fib))

with-local-vars only provides thread-local bindings for the newly created Vars, which are popped once execution leaves the with-local-vars form; hence the need for .bindRoot.

Python: Is math.factorial memoized?

Search for math_factorial on this link and you will find its implementation in python:

http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup

P.S. This is for python2.6

---

Related Topics