When we presented the Y combinator, we said that it was very aesthetic but not so practical.

Today, we are going to show a real life application of the Y combinator: the memoization of a recursive function. # The problem

Did you ever try to memoize a recursive function?

At first glance, it seems easy, using standard memoization technique:

``````\$memoize = ->(f){
memo = {}
->(x){
if memo.has_key?(x) then
memo[x]
else
res = f[x]
memo[x] = res
res
end
}
}
nil
``````

Now, let’s create a memoized version of factorial, including a counter of the number of function calls to `factorial`:

``````\$factorial = ->(n) {
\$function_calls += 1;
if (n === 0) then
1
else
n * \$factorial[n - 1]
end
}
\$function_calls = 0

\$factorial_memo = \$memoize[\$factorial];
\$factorial_memo
``````

And indeed subsequent calls to `factorial_memo` are cached:

``````factorial_memo = \$memoize[\$factorial];
\$function_calls = 0
factorial_memo
factorial_memo
\$function_calls
``````

The function has been called only 7 times.

By the way, all the code snippets of this page are live and interactive powered by the klipse plugin:

1. Live: The code is executed in your browser
2. Interactive: You can modify the code and it is evaluated as you type

But what happens to subsequent calls with smaller numbers? We’d like them to be cached also. But they are not.

Here is the proof:

``````factorial_memo = \$memoize[\$factorial];
\$function_calls = 0
factorial_memo
factorial_memo
\$function_calls
``````

The function has been called 13 times.

The reason is that the code of `factorial_memo` uses `factorial` and not `factorial_memo`.

In `ruby`, we could modify the code of `factorial` so that it calls `factorial_memo`, but it is very very ugly: the code of the recursive function has to be aware of its memoizer!!!

``````\$factorial_ugly = ->(n) {
\$function_calls += 1;
if (n === 0) then
1
else
n * \$factorial_memo_ugly[n - 1]
end
}
\$factorial_memo_ugly = \$memoize[\$factorial_ugly];

\$function_calls = 0
\$factorial_memo_ugly
\$factorial_memo_ugly
\$function_calls
``````

With the Y combinator we can solve this issue with elegance.

# The Y combinator for recursive memoization

As we explained here, the Y combinator allows us to generate recursive functions without using any names.

As envisioned by Bruce McAdam in his paper Y in Practical Programs and exposed here by Viksit Gaur, we are going to tweak the code of the Y combinator, so that it receives a wrapper function and apply it before executing the original function. Something like this:

``````\$Ywrap = ->(wrapper_func, f) {
->(x) {
x[x]
}[->(x) {
f[wrapper_func[->(y) {
x[x][y]
}]]
}]
}
nil
``````

You can compare it to the original Y combinator:

``````\$Y = ->(f) {
->(x) {
x[x]
}[->(x) {
f[->(y) {
x[x][y]
}]
}]
}
nil
``````

And here is the code for a memo wrapper generator:

``````\$memo_wrapper_generator = ->(){
memo = {}

->(f){
->(x){
if memo.has_key?(x) then
memo[x]
else
res = f[x]
memo[x] = res
res
end
}
}}
nil
``````

It is almost the same code as the `memoize` function we wrote in the beginning of this article.

And now, we are going to build a Y combinator for memoization:

``````\$Ymemo = ->(f){
\$Ywrap[\$memo_wrapper_generator[], f]
}
nil
``````

And here is how we get a memoized recursive factorial function:

``````\$factorial_gen = ->(f) {
->(n) {
\$function_calls += 1;
if (n === 0) then
1
else
n * f[n - 1]
end
}
}

\$factorial_memo = \$Ymemo[\$factorial_gen]
\$factorial_memo
``````

And here is the proof that it is memoized properly:

``````\$factorial_memo = \$Ymemo[\$factorial_gen];
\$function_calls = 0
\$factorial_memo
\$factorial_memo
\$function_calls
``````

Isn’t it elegant?

# Fibonacci without exponential complexity

The worst effective implementation (exponential complexity) of the Fibonacci function is the recursive one:

``````\$fib = ->(n) {
if (n < 2) then
1
else
\$fib[n-1] + \$fib[n-2]
end
}
nil
``````

There are a couple of effective implementations for the Fibonacci sequence without using recursion.

Using our `Ymemo` combinator, one can write an effective recursive implementation if the Fibonnaci sequence:

``````\$fib_gen = ->(f){
->(n) {
if (n < 2) then
1
else
f[n-1] + f[n-2]
end
}
}

\$fib_memo = \$Ymemo[\$fib_gen]
\$fib_memo
``````

Let’s compare the performances of the naive recursive version and the memoized recursive:

First, let’s load a timing function named `JST.time` code from github Javascript Toolbet: it works like `console.time` but with two differences:

1. It returns the elapsed time instead of printing it
2. The elapsed time resolution is fraction of milliseconds
``````def timing
a = Time.new.to_f
yield
elapsed = (1000*(Time.new.to_f - a)).round(5)
elapsed.to_s + " msec"
end
``````

And now, let’s compare:

(We have to redefine `fib_memo`, in order to reset the cache each time we re-run the code snippet.)

``````n = 27
\$fib_memo = \$Ymemo[\$fib_gen]
[
timing {\$fib[n]},
timing {\$fib_memo[n]}
]
``````

On my computer, the memoized one is around 300 times faster!