I need some help with some homework. I am not that familiar with python. However, I have some problem with this small python program. It uses recursion to print out a set of number based on the function given. It gets to about num = 30 and the program crashes. Not sure what is wrong or how to fix it. help?
def func(num):
if num==0:
return 0
elif num==1:
return 1
else:
return func(num-1)+2*func(num-2)
for num in range(2,101):
print(num,func(num))
It doesn't crash but the number of recursion becomes big and it takes too long to calculate, you can use memoization to speed things up in recursion by passing a dictionary to store the values that were already calculated and then you can easily retrieve it from the dictionary instead of calculating again. You also don't need to use elif/else when if you are returning a value inside your if-statement, for example:
def func(num, m):
if num == 0:
return 0
if num == 1:
return 1
if num not in m:
m[num] = func(num-1, m)+2*func(num-2, m)
return m[num]
m = {}
for num in range(2,101):
print(num,func(num, m))
functools.lru_cache?
functools.lru_cache is not available in python 2 afaikprint function. But you're right, it's only in Python 3.
m on each loop iteration? BTW, it'd be faster to do if num not in m rather than try...except KeyError since the exception gets raised fairly frequently.m outside the loop and check if num not in m instead of try/except. Edited, thanks
StackOverflowError? Each function call has to allocate a new stack, so you're probably using a lot of resources upon each call.