On Jul 13, 7:56 am, Steven D'Aprano <[EMAIL PROTECTED] cybersource.com.au> wrote: > On Sat, 12 Jul 2008 19:25:18 -0400, Terry Reedy wrote: > > ssecorp wrote: > >> def fib(n): > >> def fibt(a, b, n): > >> if n <= 1: > >> return b > >> else: > >> return fibt(b, a + b, n - 1) > >> if n == 0: > >> return 0 > >> else: > >> return fibt(0, 1, n); > > >> and can memoization speed up this even more? tesintg with memoization > >> doesnt really say anything because it is so fast it is instant anyway. > > > Except for the fact that a+b gets slower as a and b get bigger, this > > would already be linear time in n. Memoization (here by means of a > > linear list) only helps if the list is preserved and one makes repeated > > requests for various fib values. > > > I am just curious what input you tried that blew the stack? It had to > > be pretty large. > > No, not really. Try it for yourself: on my system, I get RuntimeError: > maximum recursion depth exceeded with fib(999). > > fib(999) is a large number, with 208 digits, but not that large: > > 268638100244853593861467272021429239676166093189869523401 > 231759976179817002478816893383696544833565641918278561614 > 433563129766736422103503246348504103776803673341511728991 > 69723197082763985615764450078474174626L > > -- > Steven
The default CPython recursion limit is 1000 - so hitting it with an input of 999 is not that surprising... You can set a higher limit with sys.setrecursionlimit(...) Michael Foord http://www.ironpythoninaction.com/ -- http://mail.python.org/mailman/listinfo/python-list
