Just started learning about Dynamic Programming and memoization using generation of the nth Fibonacci number as an example. I wrote the following code (actually took help from a website), erased it and tried to write it once myself. There is a problem with the return call (TypeError) that I can't understand.
I fixed it by indenting the return memo[x] call below the if statement and the program worked.
I just want to know the reason for the error in the following code:
What does the code do?
1) Creates a function to memoize an input function
2) Sub function 'helper', which checks if the output of the entered function is in the dictionary called 'memo'. If not, then it updates the dictionary as required
The entire function returns a number from memo (if it's already in memo) to avoid unnecessary branching.
3) Creates a function to generate Fibonacci numbers by using the recursion algorithm.
4) Memoizes the Fib No. generator and print the nth Fib No.
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
def fib(n):
if n==0:
return 0
if n == 1:
return 1
else:
return fib(n-1)+fib(n-2)
fib = memoize(fib)
print(fib(10))
I expect it to return the nth Fib. No. but instead it returns an error in the return memo[x] call.
Error Message:
Traceback (most recent call last):
File "E:\euler25.py", line 18, in <module>
print(fib(10))
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
File "E:\euler25.py", line 5, in helper
memo[x] = f(x)
File "E:\euler25.py", line 14, in fib
return fib(n-1)+fib(n-2)
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'
[Finished in 0.1s with exit code 1]
What does this error message mean?
memo
, so it implicitly returns None. Un-indent (shift+tab) yourreturn
line. ;) – h4z3 Aug 12 at 8:41