Naive Recursion faster then Memoized recursion

Question

I am a beginner to python, and was following this video for learning dynamic programming. For the case of finding a Fibonacci series, the tutor introduced memoization to improve the performance of the recursive algorithm. The complete code is as follows

    import time

def fibonacci1(n):
    '''This uses the naive fibonacci algorithm. '''
    if n < 2:
        return n
    else:
        return fibonacci1(n-1) + fibonacci1(n-2)

def fibonacci2(n):
    ''' This function uses a memo of computed values to speed up the process'''
    memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    f = fibonacci2(n-1) + fibonacci2(n-2)
    memo[n] = f
    return f

def screen(i,N):
    if i==1:
        return fibonacci1(N)
    if i == 2:
        return fibonacci2(N)

N = int(input("Enter a number: "))

for i in range(2):
    t0 = time.time()
    fib = screen(i+1,N)
    print("The "+ str(N) +"th fibonacci number is {}".format(fib))
    t1 = time.time()
    print("Time taken is : {}s".format(t1-t0))

But this is the output I received: FibonacciOutput

Can somebody help me with this?

Answer 1

What's happening here is that your memo is a local variable, which you're assigning an empty dict into at the beginning of each run of fibonacci2. Thus, you will never find n inside of memo.

There are various ways of accomplishing what you're trying to do. One of them (not the greatest, but at least simple to understand) is using a global variable:

memo = {}
def fibonacci2(n):
    ''' This function uses a memo of computed values to speed up the process'''
    global memo
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    f = fibonacci2(n-1) + fibonacci2(n-2)
    memo[n] = f
    return f

Here we defined memo outside of the function, so it only gets defined one time. The global memo line indicates that the memo we're using in our function was actually defined outside of it.