Python “yield” and Project Euler problem 2

When working on Project Euler problem 2, I stumbled on a unique feature of Python: the yield keyword. The yield keyword allows for the creation of generators. Generators are defined much like functions, but have the added bonus of being able to return multiple values over the course of their execution. For example, lets say I wanted to make a function that counted from 0 to infinity, and kept it’s state between uses. The following generator would do just that:

```def counter():
a = 0
while True:
yield a
a += 1
```

Simple isn’t it? Iterating through it is simple too. Let’s say we want to get the first 10 numbers, and then the next 20, with a break in between:

```if __name__ == "__main__":
x = counter()
for i in x:
if i < 10:
print i
else:
break
print "Broken out of counter"
for i in x:
if i < 30:
print i
else:
break
```

The output would be:

0
1
2
3
4
5
6
7
8
9
Broken out of counter
11
12
13
.
.
.
23
24
25
26
27
28
29

Now to make this relevant. Project Euler problem 2 is as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

So what we need to do is find a way to take the starting values of 0 and 1, and as each iteration passes, set a to the value of b, and b to the value of a+b, returning a each time. Sounds like a job for generators!

```def fibonacci(max):
a, b = 0, 1
while a < max:
yield a
a, b = b, a+b
```

Next, we loop through each of the returned values, checking if it is even. If so, add it to a running total.

```def sumEvenFibonacciNumbers(max):
number = 0
for n in fibonacci(max):
if n%2 == 0:
number += n
return number

if __name__ == "__main__":
print sumEvenFibonacciNumbers(4000000)
```

There you have it, using generators Project Euler problem 2 was a breeze!

1. Candy Harris

/  March 6, 2010

Cool Thanks for the article. I am new at django and this got me straight.