Мне нужно ускорить рекурсию
Мне задали решить задачу. Я написал код, но он работает медленно. Мне нужно ускорить рекурсию. Если n будет равен даже 70 расчеты займет очень много времени.
Помогите мне улучшить мой код. Максимальное n может быть 500!
def a(n):
if n == 1:
return 1
if n == 2:
return 2
return 1 + a(n - a(a(n - 1)))
Ответы (2 шт):
Здесь есть простой способ ускорения: кешировние Завести глобальный массив, и при вычислении функции от какого то значения аргумента записывать туда результат. При следующем вызове функциии от того же значения аргумента - не вычислять её, а брать из массива готовое, уже посчитанное значение
как вариант -
дело в том, что функция a(n) вызывается многократно, а значит рекурсий больше, чем нужно
можно вычислить a(n) однократно и дальше только использовать уже вычисленные значения
res = [0 for _ in range(1000)]
def a(n):
if res[n] == 0:
if n > 2:
res[n] = 1 + a(n - a(a(n - 1)))
elif n == 1:
res[n] = 1
elif n == 2:
res[n] = 2
return res[n]
print(a(900))
a(900) работает мгновенно, так что можно считать это оптимизацией :)
только учтите одну важную вещь, я не знаю как у питона, но при рекурсии у того же c++ вызовы запихиваются в стек и стек может просто переполниться
в моем примере при n = 1000 питон уже ругается
RecursionError: maximum recursion depth exceeded in comparison
P.S.
в коде много if, поэтому лучше сделать ее покороче
res = [0, 1, 2] + [0 for _ in range(10)]
def a(n):
if res[n] == 0:
res[n] = 1 + a(n - a(a(n - 1)))
return res[n]
print(a(10))
да и вообще зачем нам эти if?
res = [0, 1, 2] + [0 for _ in range(20)]
def a(n):
res[n] = res[n] or (1 + a(n - a(a(n - 1))))
return res[n]
print(res)