Why is this blowing the stack, thought it was tail-recursive...
Steven D'Aprano
steve at REMOVE-THIS-cybersource.com.au
Sun Jul 13 08:56:20 CEST 2008
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
More information about the Python-list
mailing list