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
what R.C. is all about.



For the example for implementation I used href="http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences"
target="_blank">Hoffstadters Female and Male
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.

With that knowledge in mind I thought I might gradually jump to higher
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 :-)



- Paddy.