Fibonacci: returning a selection of the series

[Alain Ketterlin]

Baba <raoulbia at gmail.com> writes:

> 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]
[...]
> my questios:
> - would you agree that recursive is not ideal for generating a list?
> (in this particular case and in general)

I would not, in the general case. Well-known problems like fact or fib
have been scrutinized in so much detail that I find it hard to conclude
anything by looking at them. And problems producing lists are usually
"easy" to transform from one version to the other.

However in the general case, to me, the recursive version is usually
much easier to understand, and the iterative version is just an
optimization to save space. There are recursive algorithms that I would
have trouble to write in an iterative way (unless I use an explicit
stack, but that doesn't really count).

We'll stay with the iterative version here, because you've started with
that and you're not far from the solution. But when you're done, try to
think about a recursive version. When the goal is to produce a list, the
recursion scheme is almost immediate: produce one element per call, one
after the other.

> - can my code below be optimised?

Sure. What's this 12 there? Why traversing the list three times (index()
needs to traverse at least some part of it)? And...

> - how to deal with 'start' and 'end' values that are not in the list
> e.g. 4,76 ?

In general, if you have a program that produces something just to
remove/ignore it five lines later, you have a problem. In your case:

1) are you sure you need to append to list(*) at every iteration? When
do you *really* need to? And...

2) your loop runs up to n (the index of the fib number), but you want to
stop on some fib number value (not index).

So, why not pass start and end to i_fib, and use them where appropriate?

-- Alain.

(*) Don't use "list" as a name, because it's a (useful) built-in
function. Use more expressive names: fn instead of b, fn_1 instead of a,
fibnumbers instead of list, etc.

>
> def i_fib(n):
>     a = 0
>     b = 1
>     list = []
>     counter = 0
>     while counter < n:
>         a, b = b, a+b
>         counter += 1
>         list = list + [b,]
>     return list
>
> def fib_range(start,end):
>     list = i_fib(12)
>     if start in list and end in list:
>         start = list.index(start)
>         end = list.index(end)
>         print list[start:end+1]
>     else: print 'not in list'