# Project Euler: Problem 2
#
#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, ...
#
# By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
# find the sum of the even-valued terms.
##################################
# Solution: 4613732
# Time elapsed: 5.993541240692139
##################################

from time import time 

def fib(n):
    '''
        Fibonacci function
    '''
    if n == 0:
        return 1
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

def get_sum(stop = 0):
    '''
        Generate Fibonacci sequence whose values do not exceed 4000000
    '''
    condition, numbers, j = True, [], 1
    while condition:
        a = fib(j)
        if a > stop:
            condition = False
        elif a % 2 == 0:
            numbers.append(a)
        j += 1
    return numbers

start = time()
numbers = get_sum(4000000) # limit: 4000000
elapsed = time() - start
sum_numbers = sum(numbers)
print("Solution: {0} \tTime elapsed: {1}".format(sum_numbers, elapsed))