I'm learning about memoization in recursive functions and stumbled upon a fibonacci-example on Youtube. I never saw the person run the code so perhaps he wrote it wrong.
When I copied the code and tried to run it, i first got an error since I declared memo without a range, so I simply set the range to the input + 1 (since I'm not using the 0-index) and thus solved that problem. But now I'm stuck at the wrong return value.
def fib(num, memo=[]):
if num == 0:
return 0
elif num == 1 or num == 2:
return 1
elif memo[num] != None:
return memo[num]
else:
memo[num] = fib(num-1, memo) + fib(num-2, memo)
return memo[num]
uInput = int(input("Fibonacci: "))
memo = list(range(uInput + 1))
fibNum = fib(uInput, memo)
print(fibNum)
The code above throws no error but simply returns the "uInput" value. So if I input 6, for the 6st fibonacci number, the program returns 6 instead of 8, which is the actual 6st number. I am at a loss as to why this occurs.
When I have googled the issue I have found threads that suggested using dicts instead of lists. Thats all fine if that is the only way to do it. But if there is a way to make it work with a list I would like to understand how that is done so that I understand why I run in to this problem.
Accessing memo[num] will never return None. If num is out of range, a IndexError will be raised. Moreover, you typically do not want to pass a memo argument to your function and instead let it rely on its own memo object.
In your case, you want to check that the index is in range with len. Whenever num is out of range, the output must be computed recursively and memoized. Only then can it be returned.
def fib(num, memo=[0, 1]):
if num >= len(memo):
memo.append(fib(num - 1) + fib(num - 2))
return memo[num]
print(fib(10)) # 55
By the way, the above can easily be transformed into an iterative function which is typically more efficient in Python.
def fib(num, memo=[0, 1]):
while num >= len(memo):
memo.append(memo[-1] + memo[-2])
return memo[num]