# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Friday, April 10, 2009

### Memoization and stack use.

I was caught out today when investigating how to apply memoization to
allow computation of larger values of a recursive function.

## Mutual Recursion

I had thought up a new task for Rosetta Code called href="http://www.rosettacode.org/wiki/Mutual_Recursion">Mutual
Recursion, as I had remembered that some languages needed
at least the signature of a function to be defined before it
could be called, and so creating mutually recursive functions would
allow you to compare the languages in an interesting way - which is

sequences, and produced the following href="http://www.rosettacode.org/wiki/Mutual_Recursion#Python">Python
definitions:

`def  color="#008080">F(n): return 1  color="#804040">if n == 0  color="#804040">else n - M(F(n-1)) color="#804040">def  color="#008080">M(n): return 0  color="#804040">if n == 0  color="#804040">else n - F(M(n-1))`

It seems that other members of R.C. liked the task and soon added many
examples in other languages.

Apart from the computation of the series for 0<=n<20, I
did try to compute F(200) but it blew the stack so I went to bed and
decided to memoize the functions another day.

## target="_blank">Wot, no memoize?

Memoization came very easily to mind, so I thought that Python would
have such available as a decorator waiting to be applied. No such luck,
I would have to craft my own . I did remember correctly however that
there was some  helper function that made wrapped functions
look a lot more like what had been wrapped, and so used functools.wrap:

`from functools  color="#a020f0">import wraps color="#804040">def  color="#008080">memoize0(func):    ' color="#ff00ff"> Adds cache as attribute to wrapped function for ease of access'     color="#a020f0">@wraps(func)     color="#804040">def  color="#008080">wrapper(*args):        argsl = tuple(args)         color="#804040">if argsl  color="#804040">in wrapper._cache:             color="#804040">return wrapper._cache[argsl]         color="#804040">else:             color="#804040">return wrapper._cache.setdefault(argsl, func(*args))    wrapper._cache = dict()     color="#804040">return wrapper color="#804040">def  color="#008080">memoize(func):    ' color="#ff00ff"> Creates closure around locally created cache'    cache = dict()     color="#a020f0">@wraps(func)     color="#804040">def  color="#008080">wrapper(*args):        argsl = tuple(args)         color="#804040">if argsl  color="#804040">in cache:             color="#804040">return cache[argsl]         color="#804040">else:             color="#804040">return cache.setdefault(argsl, func(*args))     color="#804040">return wrapper`

I haven't got over my (probably infantile) lust for attaching
attributes to functions so justified memoize0 as it allows you to look
at the contents of the cache. Combined with the fact that you cannot do
a memoization decorator without applying it to a href="http://en.wikipedia.org/wiki/Fibonacci_function">Fibonacci
number function:

`if __name__ == ' color="#ff00ff">__main__':     color="#a020f0">@memoize0     color="#804040">def  color="#008080">fib(n): return n  color="#804040">if n  color="#804040">in (0,1)  color="#804040">else fib(n - 1) + fib(n - 2)     color="#a020f0">@memoize0     color="#804040">def  color="#008080">fib2(n):  color="#804040">return n  color="#804040">if n  color="#804040">in (0,1)  color="#804040">else fib2(n - 1) + fib2(n - 2)     color="#804040">assert fib._cache  color="#804040">is  color="#804040">not fib2._cache    fib(50); fib2(50)     color="#804040">assert fib._cache == fib2._cache  color="#804040">and (fib._cache  color="#804040">is  color="#804040">not fib2._cache)`

It is important that caches are not shared for mutually recursive
functions.

## A blown stack

I had initial success with the Male and Female sequence and was easily
able to compute F(200) with:

`    @ color="#008080">memoize     color="#804040">def  color="#008080">F(n):        ' color="#ff00ff"> Hofstadters Female Male sequences'         color="#804040">return 1  color="#804040">if n == 0  color="#804040">else n - M(F(n-1))     color="#a020f0">@memoize     color="#804040">def  color="#008080">M(n):        ' color="#ff00ff"> Hofstadters Female Male sequences'         color="#804040">return 0  color="#804040">if n == 0  color="#804040">else n - F(M(n-1))     color="#804040">assert F(200) == 124`

But I got cocky, as F(2000) ran out of stack.

A little thought made me realise that I only had a cached results for F
and M up to around 200 and so a call of F(2000) was going to eat up
huge amounts of stack before recursing down to cached values.

values of  n and, indeed, the following worked:

`    print ([F(n)  color="#804040">for n  color="#804040">in range(0,20000+1,100)])`

In real-world applicatrions, you might have to have some scheme to
reduce or limit cache size if memory rather than the stack becomes an
issue, and I have a great solution that I have just completed in the
margin :-)

1. Look up Dynamic Programming in Wikipedia. There's a natural way to reverse the computation of a memoized function from the bottom up and avoid stack limits.

2. Hi Marius,
I took a look and Dynamic programming, according to WP, has two methods:
1) Recursion and memoization - which I am applying above.
2) The bottom-up approach which amounts to changing recursion into iteration - which I didn't want to do in this case as I was purposefully playing with recursion.

Thanks for the input though.

3. See sys.setrecursionlimit().
Python's default limit is 1000.
Note that the wrapper increases the stack depth by 2 - e.g. to compute F(2000) you want to allow 4000 depth.