On 2010-09-01, Albert van der Horst <alb...@spenarnc.xs4all.nl> wrote:
> [Didn't you mean: I don't understand what you mean by
> overlapping recursions? You're right about the base case, so
> clearly the OP uses some confusing terminology.]
>
> I see a problem with overlapping recursions. Unless automatic
> memoizing is one, they are unduely inefficient, as each call
> splits into two calls.
>
> If one insists on recursion (untested code, just for the idea.).
>
> def fib2( n ):
> ' return #rabbits last year, #rabbits before last '
> if n ==1 :
> return (1,1)
> else
> penult, ult = fib2( n-1 )
> return ( ult, ult+penult)
>
> def fub( n ):
> return fib2(n)[1]
>
> Try fib and fub for largish numbers (>1000) and you'll feel the
> problem.
There are standard tricks for converting a recursive iteration
into a tail-recursive one. It's usually done by adding the
necessary parameters, e.g.:
def fibr(n):
def fib_helper(fibminus2, fibminus1, i, n):
if i == n:
return fibminus2 + fibminus1
else:
return fib_helper(fibminus1, fibminus1 + fibminus2, i+1, n)
if n < 2:
return 1
else:
return fib_helper(1, 1, 2, n)
Once you've got a tail-recursive solution, you can usually
convert it to loop iteration for languages like Python that favor
them. The need for a temporary messed me up.
def fibi(n):
if n < 2:
return 1
else:
fibminus2 = 1
fibminus1 = 1
i = 2
while i < n:
fibminus2, fibminus1 = fibminus1, fibminus2 + fibminus1
i += 1
return fibminus2 + fibminus1
It's interesting that the loop iterative solution is, for me,
harder to think up without doing the tail-recursive one first.
--
Neil Cerutti
--
http://mail.python.org/mailman/listinfo/python-list
