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.
Fibonacci is always entertaining, but I detest how most programming courses use it as an example for explaining recursion. It's a waste of resources for something that can be done pretty simply, and even more simple in Python.
One of Python's incredibly magnificent data structures is the list. It's sort of like an array, in which you can get the value of an indexed position in the list by providing the index, but at the same time, it's not as inflexible as an array. And though most languages include a data structure that represents a dynamic list, Python's version is just way beyond cool.
Here's an example of a list:
randomlist = ['A', 5, "llamas"]
The list randomlist now contains three elements; the index of the first element is 0 (just because that's how computers count).
>>> randomlist[0]
'A'
>>> randomlist[1]
5
>>> randomlist[2]
"llamas"
(Notice how Python lets you quote strings using either single or double quotes? Also, it doesn't restrict what you dump into a list, like some other languages where you have to declare the type of the items you'll add to the list.)
So let's see how our professors taught us Fibonacci:
function fib(n):
if n = 1 or n = 2
return n
else
return fib(n-1) + fib(n-2)
end if
So to calculate fib(5), you have to calculate fib(4) and fib(3). But to calculate fib(4), you have to calculate fib(3) and fib(2), so you've wasted time calculating fib(3) twice. The same happens with fib(2), calculated in fib(4) and fib(3) (Yes, fib(2) is just 2, but we're sticking to principle here.)
And as if this weren't bad enough, every time you call a function, you're taking up memory. A function call will reside in an area of memory called the stack until it has returned something. So aside from calculating fib(3) twice, you're taking up twice the memory as well, until those calls get their result.
Now, let's use a much more reasonable way of calculating this:
fiblist = [1, 2]
if n <>
How does Python improve on this? Well, to get the last element of a list, you could get the value of the length of the list, subtract 1 and use that as the index. But Python already anticipated this as something that it should provide, so it takes the hard work out of it. To get the last element of fiblist, use fiblist[-1]. To get the second-to-last element, use fiblist[-2].
Now, how about adding something to the end of a list? Simple. Just use fiblist.append(newelement) to add newelement to the end of the list.
The above rigmarole gives you the list of Fibonacci elements, but how do you get just the even ones, like the problem requires? Well, you still need all of the elements of the sequence to calculate the next one, but we can capture just the even ones as we're generating the list, and add them to a running total, like we did in Problem 001:
while x <>
This will start a block of code that will continue until the value of x is greater than 4 million.
x = fiblist[-1] + fiblist[-2]
To add the last two elements in the list.
if x % 2 = 0:
total = total + x
If x is even, add it to the running total (remember to zero out the total at the beginning!)
fiblist.append(x)
Add x to the end of the list, ready for the next calculation to use it.
It's interesting that the Fibonacci sequence has a pattern in the parity of its elements:
1, 2, 3, 5, 8, 13, 21, 34, 55, ...
O E O O E O O E O
How come? Well, the sum of two odd numbers or two even numbers is always even, and the sum of an even number and an odd number is always odd. See how the even number sticks around just long enough to get the next two numbers to be odd, guaranteeing that just as it leaves the two-element window, the next element to be added is even.
Ain't math grand?
