On Apr 30, 11:14 am, Peter Otten <__pete...@web.de> wrote:
> For the record, the one true way to implement the Fibonacci series in Python
> is
>
> >>> def fib():
>
> ... a = b = 1
> ... while True:
> ... yield a
> ... a, b = b, a+b # look ma, no temporary variable
Not any claim to 'the one true pythonic way' but fib can be written in
a clean recursive way with linear space-time behavior asz follows:
Dijkstra explained that fib is an 2nd order recurrence
-- fib(n) defined in terms of fib (n-1) and fib(n-2)
whereas programming loops and recursion are 1st order -- state at
iteration n defines state at iteration n+1.
Converting the 2nd order fib relation to a 1st order one trivially
gives a linear program.
The key insight from Dijkstra is that all we need to do is to move
from a recursive function returning fibonacci nos to one returning
pairs of adjacent ones.
def fibpair(n):
# returns (fib(n), fib(n+1))
if n==0:
return (1,1)
else:
(a,b) = fibpair(n-1)
return (b, a+b)
After that fib is just this:
def fib(n):
a,b = fibpair(n)
return a;
--
http://mail.python.org/mailman/listinfo/python-list
