Fibonacci: returning a selection of the series

[Steven D'Aprano]

On Sun, 29 Aug 2010 10:36:45 -0700, Baba wrote:

> level: beginner
> 
> i would like to return a selection of the Fibonacci series. example:
> start = 5 ; end  = 55
> the function should then return [5, 8, 13, 21, 34, 55]

Start with something to lazily generate Fibonacci numbers. It doesn't 
matter whether this is iterative or recursive, but it must be *lazy* -- 
only generating each number when you ask for the next one. Generators are 
ideal for this:

# Untested.
def fib():
    """Generate the Fibonacci numbers."""
    a, b = 1, 1
    yield a
    while 1:
        yield b
        a, b = b, a+b


Then pass it into a filter than skips numbers less than start, 
accumulates numbers until you exceed end, and stop. Then return the 
numbers that you collected.



> it seems that this is best resolved using an iterative approach to
> generate the series. In another post (http://groups.google.ie/group/
> comp.lang.python/browse_thread/thread/aa85ac893fd89c4a/
> d3803a93baf1bdd0#d3803a93baf1bdd0) i looked at the recursive approach
> which seems best to compute the nth number but it seems to me that the
> recursive code is not suited for generating the actual list.

In this specific case, you can get recursion to be much, much more 
efficient than the naive f(n) = f(n-1) + f(n-2) case, but iteration in 
Python is often more efficient.


> my questios:
> - would you agree that recursive is not ideal for generating a list? (in
> this particular case and in general) 

In this particular case, an iterative approach to Fibonacci will probably 
be more effective.

In general, no, recursion is fine for generating lists.


-- 
Steven