Revision history [back]

Your code is probably not well copied since the function f directly returns something, so what is after that will never be executed.

Anyway, here is an example on how to memoize a recursive function:

sage: @cached_function
....: def fibo(n):
....:     if n == 0 or n == 1:
....:         return 1
....:     else:
....:         return fibo(n-1) + fibo(n-2)

You can see the difference by calling fibo(100) with and without the @cached_function decorator.

Now, if you want to compute, say, fibo(1000), you may encounter a RuntimeError: maximum recursion depth exceeded. So the trick is to fill the memory in the right order:

sage: for i in range(1000):
....:     a = fibo(i)
sage: fibo(1000)
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501