Fibonacci and yield

Look at this problem 25 from euler project below:

Yes it is simple recursion:

	def fibo(i):
	if i == 1 or i == 2:
	return 1
	return fibo(i-1) + fibo(i-2)
	count = 10
	while True:
	f = fibo(count)
	if len(str(f)) == 1000:
	print "got", f
	break
	count += 1

view raw lame.py hosted with ❤ by GitHub

But this one is like running forever. Considering the fact it needs the first number with 1000 digits, not surprising.

Then I start browsing and googling, met this one, using yield to generate fibonacci number; hell, when I saw the word "yield" I was like YEAH THATS IT:

	def fibo_gen():
	a = 1
	b = 1
	while 1:
	yield a
	a, b = b, a+b
	a = fibo_gen()
	f = a.next()
	count = 1
	while 1:
	if len(str(f)) == 1000:
	print count
	break
	f = a.next()
	count += 1

view raw awesome.py hosted with ❤ by GitHub

When I run it I almost wet myself. So fast that makes you cant help but sing a song about it.

Basically, it returns a generator. Generator in python is lazy, it never actually calculates the next one until you force it by calling next. Old version every time it generates a new fib number, it goes to the very first and runs back one by one later. When number gets big the problem is like hell. Use generator however, you only do one addition every time, plus, in the while loop, you only return one number each time. Well I dont know you, but to a python rookie like me...


what happens to the old version? Still running.