maximum recursion depth exceeded in cmp

[agi]

Hi,
I have a recursive algorithm that works well if it doesn't need more
than 5637 iterations.
In the case of more than 5637 iterations the error message is:
RuntimeError: maximum recursion depth exceeded in cmp

Is there a way to make SAGE execute it for more than 5637 iterations?

[adrian]

This is a dirty solution, but it might be interesting:

It is possible to implement "tail recursion"; this would solve the
problem for certain kinds of recursion; but will fail if the call is
not a tail call, and I think this code won't work, but some variations
would...

I toss it as an idea:

The code is taken from http://code.activestate.com/recipes/474088

import sys

class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.

This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func

@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)

print factorial(10000)
prints a big, big number,
but doesn't hit the recursion limit.

@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)

print fib(10000)

also prints a big number,
but doesn't hit the recursion limit.

@tail_call_optimized
def say(something):
print something
say(something)
say('hello')

If I remember correctly, this code breaks and hangs the computer if
the tail is not a tail call; but there seems to be other solutions in
http://code.activestate.com/recipes/474088 that solve this problem

I would love if sage included a similar decorator; but am not sure of
the implications.

Another alternative is rewriting your code... to use iterations
instead of recursion whenever possible.

Peace.
-Adri'an.

[William Stein]

This is a general Python question. Searching for python and "maximum
recursion depth" in google gives numerous pages with the answer, which
is to call

sys.setrecursionlimit(limit)

as documented here: http://docs.python.org/library/sys.html

" Set the maximum depth of the Python interpreter stack to limit. This
limit prevents infinite recursion from causing an overflow of the C
stack and crashing Python.

The highest possible limit is platform-dependent. A user may need
to set the limit higher when she has a program that requires deep
recursion and a platform that supports a higher limit. This should be
done with care, because a too-high limit can lead to a crash."

-- William

[agi]

Thanks,
sys.setrecursionlimit(limit) works.

On 26 Mrz., 16:39, William Stein <wst...@gmail.com> wrote: