Sunday, 3rd July 2011

# Python Fibonacci generator using reduce()

Khan Academy now has a series of videos on Python programming, and I've spent way too much of this weekend watching them, despite knowing all the basics of Python (I did learn a couple of things though). In fact, I spent so much time watching video, I finally broke the million point mark (and now have 77 points in binary):

Anyway, that's by-the-by and just showing off. The main point was that in one video Sal sets an exercise to create a function to return the nth Fibonacci number. The idea was to write a function either using recursion or a for loop, but having learnt a bit about Python iterators and functional programming, I wondered if there was a fanicer way to do it, using something like the reduce() function.

This is what I came up, but it's not it's not very pretty. I'm sure there must be a better way that doesn't require a generator of tuples, which doesn't do much for the most part.

def fibonacci(n): if n > 0: a = ((0,1) for _ in range(n)) return reduce(lambda x, y: (x[1], x[0]+x[1]), a)[1] else: return 0

## Comments

It's my version of this program, a little bit simpler I guess :

a = [1, 1]

for i in range(10) :

a.append( reduce( lambda x,y: x+y, a[-2:] ) )

It might be a bit simpler, but it sort of defeats the point of using reduce(). Since you're only using it on the last two items in the list, you might as well just use add:

a.append(a[-1] + a[-2])

I was trying to make use of the fact that reduce compresses a list of numbers by comparing each on to the current value, but I had to find a way to separate the previous two values.

## Post new comment