Python: What's wrong with this Fibonacci function?

Question

I tried to write a simple python function which should return the list of fib numbers upto some specified max. But I am getting this error. I can't seem to find out what I am doing wrong.

def fib(a,b,n):
    f = a+b
    if (f > n):
        return []
    return [f].extend(fib(b,f,n))

>>>fib(0,1,10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
TypeError: 'NoneType' object is not iterable

score 9 · Accepted Answer · 2011-04-23 08:31:19Z

9

list.extend extends a list in-place. You can use the + operator to concatenate two lists together.

However, your code isn't particularly Pythonic. You should use a generator for infinite sequences, or, as a slight improvement over your code:

def fib(a,b,n):
    data = []
    f = a+b
    if (f > n):
        return data
    data.append(f)
    data.extend(fib(b,f,n))
    return data

An example using generators for infinite sequences:

def fibgen(a, b):
    while True:
        a, b = b, a + b
        yield b

You can create the generator with fibgen() and pull off the next value using .next().

edited Apr 23, 2011 at 8:31

answered Apr 23, 2011 at 8:26

user193476

Sign up to request clarification or add additional context in comments.

1 Comment

Sid Over a year ago

Thanks, that did the trick. I guess another solution is to make a separate list and set that to extend() and return this new list.

Katriel · Accepted Answer · 2011-04-23 08:46:48Z

1

You may be interested in an especially neat Fibonacci implementation, though it only works in Python 3.2 and higher:

@functools.lru_cache(maxsize=None)
def fib(n):
    return fib(n-1) + fib(n-2) if n > 0 else 0

The point of the first line is to memoise the recursive call. In other words, it is slow to evaluate e.g. fib(20), because you will repeat a lot of effort, so instead we cache the values as they are computed.

It is still probably more efficient to do

import itertools
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)
nth(fibgen())

as above, because it doesn't have the space overhead of the large cache.

answered Apr 23, 2011 at 8:46

Katriel

124k19 gold badges141 silver badges172 bronze badges

Collectives™ on Stack Overflow

Python: What's wrong with this Fibonacci function?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related