Project Euler #2 - Even Fibonacci numbers Given:

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.

MAX_LIMIT = 4000000 # Four million inclusive
FIB_CACHE = {}

def fib(n):
    &quot;&quot;&quot; Calculates nth fibonacci term.
    Args:
        n: The nth term.
    Returns:
        The nth fibonacci term of the series.
    &quot;&quot;&quot;
    if (2 &gt;= n):
        return n
    if (n not in FIB_CACHE):
        FIB_CACHE[n] = fib(n-1) + fib(n-2) # linear recurrence
    return FIB_CACHE[n]
    
def sum_fib():
    sum = 0
    i = 1
    ith_fib = 0
    while (1):
        ith_fib = fib(i)
        if (ith_fib &gt; MAX_LIMIT):
            return sum
        if (ith_fib % 2 == 0):
            sum += ith_fib
        i += 1
    return sum
    
print fib(1)
print fib(2)
print fib(10)
print sum_fib()

Note: Without caching, it was taking too long to complete since it's an exponential algorithm.
Few important points:

I read somewhere about putting fewer changing values on the left. Is this true?
I am always confused about when to use an if-if branch and anif-else branch. Is there any heuristic? For example, could I write cache-checking code in the else branch too?
Going from top to bottom:

MAX_LIMIT = 4000000 # Four million inclusive


That sounds like a function parameter, not a global constant:

def sum_fib(max_limit=4000000):
    ...


Now, you have this function:

def fib(n):
    ...


But you don't really need it. You never need the nth Fibonacci number here, out of the blue. You're always going in order. If you're going in order, you can just keep them as local variables and update both:

cur, prev = cur+prev, cur


And then:

while (1):


Typically we'd say while True:, but in this case, we have a clearly established termination condition: our max limit. So let's use it:

def sum_fib(max_limit=4000000):
    cur, prev = 1, 0
    total = 0 
    while cur &lt; max_limit:
        if cur % 2 == 0:
            total += cur 
        cur, prev = cur+prev, cur 

    return total


We could even generalize this more by providing a predicate:

def sum_fib(max_limit=4000000, pred = lambda x: x%2 == 0): 
    cur, prev = 1, 0
    total = 0 
    while cur &lt; max_limit:
        if pred(cur):
            total += cur 
        cur, prev = cur+prev, cur 

    return total




Now back to optimizations. What are the Fibonacci numbers? They are:

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


What are the even Fibonacci numbers? They are:

2, 8, 34, 144, 610


Notice that it's every 3rd Fibonacci number. What can we do with that? That's still a Fibonacci-like sequence. Except instead of an = an-1 + an-2, we have an = 4an-1 + an-2:

def sum_fib(max_limit=4000000):
    cur, prev = 2, 0
    total = 0 
    while cur &lt; max_limit:
        total += cur 
        cur, prev = 4*cur+prev, cur 

    return total