Search code examples
pythonfibonaccimemoization

Fibonacci Memoization in Python

I wrote this code to calculate the nth Fibonacci number and it works (calculates the right number) but fails because the table doesn't get updated. Anybody know why?

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2:
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    #return table ##This was part of my original solution but I removed it because it wasn't working
fib3(12)

This is the error I get that I think is caused by a non-updating table (since table[n] always = -1):

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'
Solution

  • You have missed returning the value for fib3 function

    import numpy as np

# memoization
n = 12
table = np.ones(n+1)*-1
def fib3(n):
    if table[n]==-1:
        if n<=2: 
            table[n] = 1
        else:
            table[n] = fib3(n-1)+fib3(n-2)
    return table[n]
fib3(12)

144