Fibonacci sum with memoization

Problem:


Using the recursion approach, find a Fibonacci sum without repetition of computation.

def sum_fibonacci(n):
    """Compute the nth Fibonacci number.

    >>> sum_fibonacci(35)
    9227465
    >>> sum_fibonacci(10)
    55
    >>> sum_fibonacci(0)
    0
    >>> sum_fibonacci(1)
    1
    >>> sum_fibonacci(5)
    5
    """
    """Your code here"""

Solution:

fibcache = {}
def  sum_fibonacci(n):
    """Compute the nth Fibonacci number.

    >>> sum_fibonacci(35)
    9227465
    >>> sum_fibonacci(10)
    55
    >>> sum_fibonacci(0)
    0
    >>> sum_fibonacci(1)
    1
    >>> sum_fibonacci(5)
    5
    """
    if n == 0:
        fibcache[n] = 0
        return fibcache[n]
    elif n == 1:
        fibcache[n] = 1
        return fibcache[n]
    else:
        sum_left = 0
        sum_right = 0
        if n-2 in fibcache.keys():
            sum_left += fibcache[n-2]
        else:
            sum_left += sum_fibonacci(n-2)
            fibcache[n-2] = sum_left
        if n-1 in fibcache.keys():
            sum_right += fibcache[n-1]
        else:
            sum_right += sum_fibonacci(n-1)
            fibcache[n-1] = sum_right
        return sum_left + sum_right

This program uses dictionary data model amidst tree recursion.

Can it be more readable? Can it avoid global cache fibcache update? Because nonlocal is better than global.

Note: I'm currently aware of data models - class 'tuple', class 'list' and class 'dict'.

I think that caching should look the same on every function,

cached_f(args):
    if args not in cache:
        cache[args] = f(args)
    return cache[args]

So Fibonacci becomes:

cache = {}    
def fib(n):
    if n not in cache.keys():
        cache[n] = _fib(n)
    return cache[n]

def _fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

I'm not sure why the cache should not be global (other than namespace pollution), you could end with duplication of the results and also missing a cached result making you compute again what you wanted to avoid computing.

Also, you may initialize the cache with the base cases and skip them when writing the recursion, but that is not so clean.

StackExchange Code Review Q#95554, answer score: 13