Fibonacci Memoization in Python

Question

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'

Your function does not return anything. So fib3(n-1) + fib3(n-2) makes no sense, because you're summing 2 void values. — Al.G.
– Al.G., Commented Jan 9, 2019 at 20:57
Thanks for the help. I thought table was a global since it is declared outside the function — DanGoodrick
– DanGoodrick, Commented Jan 10, 2019 at 8:31

Engineero · Accepted Answer · 2019-01-09 21:01:01Z

1

You aren't explicitly returning anything, and so your fib3 function automatically returns None. Thus your line table[n] = fib3(n-1) + fib3(n-2) evaluates to table[n] = None + None and there is no + operator defined for None.

edited Jan 9, 2019 at 21:01

answered Jan 9, 2019 at 20:59

Engineero

13k5 gold badges56 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Maximilian Burszley Over a year ago

None is a singleton, no plural.

Engineero Over a year ago

@TheIncorrigible1 technically correct, which is the best kind of correct! Will update. Also voted to close because it's essentially a typo.

DanGoodrick Over a year ago

This is the comment that most helped me understand the issue. Thanks.

DanGoodrick · Accepted Answer · 2019-01-10 16:37:58Z

0

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

edited Jan 10, 2019 at 16:37

DanGoodrick

3,2407 gold badges32 silver badges55 bronze badges

answered Jan 9, 2019 at 21:01

Chandra Sekhar

1186 bronze badges

Collectives™ on Stack Overflow

Fibonacci Memoization in Python

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related