CODEWITHSUNDEEP
pythonrecursionfibonacci
James Geddes
James Geddes

Reputation: 872

What is the most computationally efficient method to recursively calculate the Fibonacci sequence?

Here is the code I currently have.

def fibonacci(n):

    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        value = fibonacci(n - 1) + fibonacci(n - 2)
        return value

This currently takes quite some time to calculate values greater than n = 30. Is there a more computationally efficient method to accomplish this?

Upvotes: 1

Views: 301

Answers (4)

pjs
pjs

Reputation: 19855

No need for caching/memoization. Here's a Python 3 implementation that expresses the Fibonacci sequence as powers of a matrix, then does efficient exponentiation via halving and squaring. The result is O(log n) in both time and storage.

def matrix_fib(n):
    if n == 1:
        return [0,1]
    else:
        f = matrix_fib(n // 2)
        c = f[0] * f[0] + f[1] * f[1]
        d = f[1] * (f[1] + 2 * f[0])
        return [c,d] if (n & 1) == 0 else [d,c+d]

def fib(n):
  return n if n == 0 else matrix_fib(n)[1]

print(fib(1000000))

On my laptop this coughs up the value of the millionth Fibonacci number in a little over half a second, and the bulk of that is probably in the big integer arithmetic and formatting of the output—the result is ridiculously large. You don't need to worry about stack overflow, though. The call stack depth for this is only log2(1000000) = 20.

Upvotes: 0

James Geddes
James Geddes

Reputation: 872

Adding a value cache to trade some memory for a reduced processing time can be a useful method. A purely recursive program will attempt to calculate values over and over again, however this takes time for larger values. If the values do not change, then storing them can be helpful. It is important to note, however, that should values be volatile you might need a different approach. 

fibonacci_value_cache = {}


def fibonacci(n):

    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n in fibonacci_value_cache:
        return fibonacci_value_cache[n]
    else:
        fibonacci_value_cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
        return fibonacci_value_cache[n]

n = 100

print("Fib " + str(n) + ": " + str(fibonacci(n)))

Here, we check if the value is in the dictionary and return it if it is, otherwise we calculate it and add it to the dictionary. This means that we are make better use of the processor by not calculating the same value multiple times.

Upvotes: 3

mutux
mutux

Reputation: 352

Using idea of Dynamic Programming, and store the intermediate results to save computational cost, it could be very efficient. The code below cost less than 0.02s for n=10000 on my laptop. 

def fib(n):  # return Fibonacci series up to n
    result = []
    a, b = 0, 1
    for i in range(n):
        result.append(b)
        a, b = b, a + b
    return result

Upvotes: 0

martineau
martineau

Reputation: 123453

There's a recipe for a decorator that uses as an example exactly what you want. It's named Memoize in the PythonDecoratorLibrary.

It may seem like overkill, but having the memoized decorator around could be useful for other future tasks. That said, here it is in its entirety (although I changed the print at the end):

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

@memoized
def fibonacci(n):
   "Return the nth fibonacci number."
   if n in (0, 1):
      return n
   return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(12))

Upvotes: 0

Related Questions