# Is there a kind of memoization in Sage build in?

Maple knows an option called 'remember' which allows the coding of a function with a recursive definition in a natural manner without a loss of efficiency (exponential time to compute often can be reduced to linear time). Does Sage have a similar option?

edit retag close merge delete

Sort by » oldest newest most voted

Yes.. and no. There is a memoization decorator, called CachedFunction (or cached_function), and it can be applied easily:

sage: @CachedFunction
....: def f(x):
....:         print 'slow call..'
....:     sleep(5)
....:     return x**2
....:
sage: f(10)
slow call..
100
sage: f(10)
100


(Or, equally, g = cached_function(f) or h = CachedFunction(f).)

Unfortunately you can still blow the recursion stack:

sage: @CachedFunction
....: def r(x):
....:         return 1 if x<= 1 else 1+r(x-1)
....:
sage: r(20)
20
sage: r(2000)
[...]
RuntimeError: maximum recursion depth exceeded while calling a Python object


CPython doesn't do tail-recursion optimization, so writing recursive functions isn't as natural. If you're interested, there are some ways around this but I wouldn't recommend them for production use..

more

1

You can increase the recursion depth using e.g., "import sys; sys.setrecursionlimit(10000)". However, watch out -- if you make it too big, you'll just crash Python completely.

( 2012-02-09 17:26:38 -0500 )edit

Just for clarity, that example isn't a true tail-call since you take the result and do something with it, namely adding 1.

( 2012-02-09 23:02:06 -0500 )edit

I wondered if someone was going to call me out on that. :-)

( 2012-02-10 00:56:17 -0500 )edit

answered 2012-02-10 02:55:28 -0500

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I do not know what is going on behind the scenes of decorater '@CachedFunction'. But perhaps it works similar as in this example:

def A000213(x) :
if x <= 1 : return 1
if x in dictfun : return dictfun[x]
dictfun[x] = A000213(x-3) + A000213(x-2) + A000213(x-1)
return dictfun[x]

dictfun = dict([])
A000213(20)

more

Kind of (although it checks "if x in dictfun" first). You can read the documentation by typing CachedFunction? and look at the actual source code for the decorator by typing CachedFunction??.

( 2012-02-10 03:18:59 -0500 )edit