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?
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..
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.
Just for clarity, that example isn't a true tail-call since you take the result and do something with it, namely adding 1.
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)
Asked: 2012-02-09 16:21:57 +0100
Seen: 1,384 times
Last updated: Feb 10 '12
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.