CODEWITHSUNDEEP
pythoniteratorfibonacci
Sid
Sid

Reputation: 129

Python: What's wrong with this Fibonacci function?

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

Upvotes: 1

Views: 537

Answers (2)

Katriel
Katriel

Reputation: 123632

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.

Upvotes: 1

user193476
user193476

Reputation:

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().

Upvotes: 9

Related Questions