7
\$\begingroup\$

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'.

\$\endgroup\$
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ See also: Fast Fibonacci algorithms, for better implementations of _fib(). Given that _fib() will take most of the time when using this implementation, it may be worth improving. \$\endgroup\$ – esote Jul 27 '18 at 1:31
5
\$\begingroup\$

If you don't like global variables (which you really shouldn't!), you can create a static variable by making it an attribute of the function:

def fib(n):
    if n in fib.cache:
        return fib.cache[n]
    ret = fib(n-2) + fib(n-1)
    fib.cache[n] = ret
    return ret
fib.cache = {0: 1, 1: 1}

Memoization is one of the poster childs of function decorators in Python, so an alternative approach would be something like:

class Memoize(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}
    def __call__(self, *args):
        if args in self.cache:
            return self.cache[args]
        ret = self.func(*args)
        self.cache[args] = ret
        return ret

@Memoize
def fib(n):
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)
\$\endgroup\$
2
\$\begingroup\$

Memoization is not strictly needed to avoid to repeat computations

def fib(n):
    (x,y) = fibpair(n)
    return y

def fibpair(n):
    if n == 0:
       return (1,0)
    else:
       (x, y) = fibpair(n-1)
       return (x+y, x)

The functions are linked by the relation

fibpair(n) == (fib(n+1), fib(n))

Edit: if you dont like the idea of computing also fib(n+1) when you need fib(n), you can also start from

fp(n) == (fib(n), fib(n-1))

with a fictious value of 1 for fib(-1) to preserve the recurrence relation.

def fib(n):
    (x, y) = fp(n)
    return x    
def fp(n):
    if n==0:
        return (0, 1)
    else:
        (x,y) = fp(n-1)
        return (x+y, x)
\$\endgroup\$
  • \$\begingroup\$ Are you computing fib(n+1) too? Also, using a loop seems clearer than that if you won't use memoization \$\endgroup\$ – Dietr1ch Jul 3 '15 at 0:33
  • \$\begingroup\$ 1) This is essentially the same as the classical iterative solution, where the loop is is represented by terminal recursion. But recursion was required, so... 2) Yes it computes an extra value. We can also start from a fictious value fib(-1) = 1. Or add tests. See edit. \$\endgroup\$ – Michel Billaud Jul 3 '15 at 8:09
  • \$\begingroup\$ I know it's the same, but it's definitely harder to understand for newcomers. It's also harder to generalize for other kind of recursions, as you have to state how the previous values will be needed. \$\endgroup\$ – Dietr1ch Jul 3 '15 at 14:06
  • 1
    \$\begingroup\$ Welll in fact it depends how much newcomers have been exposed to imperative programming. They have to twist their mind first to adapt to iterative logic. And then you ask them to see things recursively.... But simple algebra suffices here : fp(n) = (fib(n), fib(n-1)) = (fib(n-1)+fib(n-2), fib(n-1)) by definition of fib. And thus fp(n) = (x+y, x) where (x,y)=fp(n-1). \$\endgroup\$ – Michel Billaud Jul 3 '15 at 14:34
1
\$\begingroup\$

No need for global variables or two function declarations:

def fib(a, cache={0:1,1:1}):
    if a in cache: return cache[a]                                                                                 
    res = fib(a-1, cache) + fib(a-2, cache)                                                                        
    cache[a] = res                                                                                                 
    return res      

cache should be initialized as 0:0, 1:1 your solution is returning answer for a + 1 th

\$\endgroup\$

protected by Jamal Jan 10 at 4:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.