3 months, 4 weeks

Fibonacci Sequence

The Fibonacci sequence is a series of numbers in which each number is the sum of the two that precede it. Starting at 0 and 1, the sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on forever. The Fibonacci sequence can be described using a mathematical equation: Xn+2= Xn+1 + Xn


def fibonacci(n):                                               
     """Return all fibonacci numbers up to N. """
     result = [0]                                                   
     next_n = 1                                                   
     while next_n <=n:                                        
         next_n = sum(result[-2:])                         
     return result                                                 
[0, 1, 1]                                 
print(fibonacci(7))                                             [0, 1, 1, 2, 3, 5]                     
print(fibonacci(17))                                           [0, 1, 1, 2, 3, 5, 8, 13]           
print(fibonacci(41))                                           [0, 1, 1, 2, 3, 5, 8, 13,21,34] 


Memoization is a method used to store the results of previous function calls to speed up future calculations. If repeated function calls are made with the same parameters, we can store the previous values instead of repeating unnecessary calculations. This results in a significant speedup in calculations. In this post, we will use memoization to find Fibonacci sequence.

numCalls = 0                                                                     
def fastFib(n, memo):                                                        
    global numCalls                                                            
    numCalls += 1                                                              
    if not n in memo:                                                            
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    return memo[n]                                                             
def fib(n):                                                                          
    memo = {0:1, 1:1}                                                        
    return fastFib(n, memo)                                               
print ('fibonacci of', n,'=', result, 'numCalls = ', numCalls)

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

def fib(n):
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)
print(fib(5))            Output:    8
print([fib(n) for n in range(15)])    Output:[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]


What if I just wanted to iterate over those numbers?

def fibonacci(n):
   """Return all fibonacci numbers up to n. """
   yield 0
   if n == 0:
   a = 0
   b = 1
   while b <= n:
    yield b
   a, b = b, a + b
print(list(fibonacci(0))) # [0]
print(list(fibonacci(1))) # [0, 1, 1]
print(list(fibonacci(50))) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Python provides a generator to create your own iterator function. A generator is a special type of function which does not return a single value, instead, it returns an iterator object with a sequence of values. In a generator function, a yield statement is used rather than a return statement.

The fibonacci function is a generator function. First we yield 0, then if n is 0, we return (this will cause a StopIteration exception to be raised). If that's not the case, we start iterating, yielding b at every
loop cycle, and then updating a and b. All we need in order to be able to produce the
next element of the sequence is the past two: a and b, respectively.

def fibonacci(n):
    """Return all fibonacci numbers up to n. """
    a, b = 0, 1
   while a <= n:
     yield a
   a, b = b, a + b

One of the advantages of the generator over the iterator is that elements are generated dynamically. Since the next item is generated only after the first is consumed, it is more memory efficient than the iterator.


def fibonacci(n):                                                                                     

”””Return pair of Fibonacci numbers, F(n) and F(n-1).”””                       

       if n <= 1:                                                                                          

              return (n,0)                                                                               


             (a, b) = fibonacci(n−1)                                                              

             return (a+b, a)                                                                          


We claim that the execution of function  Fibonacci(n) takes O(n) time. Each recursive call to  Fibonacci decreases the argument n by 1; therefore, a recursion trace includes a series of n function calls. Because the nonrecursive work for each call uses constant time, the overall computation executes in O(n) time.