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 -- http://mail.python.org/mailman/listinfo/python-list
