Рекурсивная сумма работает на 500 элементах и падает на 5000
def rec_sum(a, i=0):
if i == len(a):
return 0
return a[i] + rec_sum(a, i + 1)
На списке из 500 чисел функция работает, на списке из 5000 — падает. В чём причина и что с этим делать?
- MemoryError: на каждом уровне рекурсии копируется список, поэтому память кончается
- Функция квадратичная по времени и на пяти тысячах элементов просто не успевает отработать
- Достаточно навесить @lru_cache: кэш обрежет глубину рекурсии и функция досчитает сумму
- RecursionError: превышен лимит глубины рекурсии, спасёт переписывание в цикл