Thomas Rachel wrote:
... because each recursion level 'return' calls fib() twice, and each of
those calls fib() twice, and you get the point...
yes - but they are called one after the other, so the "twice" call
counts only for execution speed, not for recursion depth.
>>> def fib(n):
>>> if n == 1:
>>> return(n)
>>> else:
>>> return (fib(n-1)+fib(n-2))
They *are not* called one after the other in the sense that there is
ever only one level of recursion with each call (not at all). Take a
closer look. Each call to fib() forces a double head, and each of those
forces another double head (now four), and so on... the recursion depth
exception of the OP testifies against your theory.
The thing about this problem that puzzles me, is why we might consider
recursion for a possible solution in the first place. In other words,
normally we consider using recursion when we need information further
down the stack then we have now... so that recursion is necessary
because each head call will not have the information it needs for
completion until the tail clean-up (coming back up the stack) provides
that information.
In the case of the fib() numbers (or the fib sequence) recursion is not
necessary for correctly handling of the problem. The simple
straight-forward obvious way to handle the problem is to calculate the
sequence outright in a straight-forward way. On the other hand, Otten's
use of yield (making a generator) makes some sense too, in the case that
we want to get the fib numbers over time without taking the time to
calculate the entire sequence up-front.
Just saying...
kind regards,
m harris
--
http://mail.python.org/mailman/listinfo/python-list
