Глубина рекурсии и кэш
Глубина рекурсии
Напишем функцию, которая ищет n-ый член арифметической прогрессии с первым элементом равным 1 и шагом 1.
def f(n):
if(n==1):
return 1
if(n>1):
return f(n-1)+1
Допустим нам нужно посчитать f(500), программа будет работать следующим образом f(500)=f(499)+1=f(498)+2=f(497)+3=...=f(2)+498=f(1)+499=500, таких шагов мы выполним 500 штук. Это количество шагов и является глубиной рекурсии. По умолчанию в python максимально возможная глубина рекурсии равна 1000, если верить документации. Некоторые задания требуют глубины, которая больше, чем установлена в python по умолчанию.
В этом случае мы можем увидеть следующий текст ошибки:
RecursionError: maximum recursion depth exceeded in comparison
Для решения этой проблемы у нас есть возможность изменить глубину рекурсии в каждом отдельном случае. Для этого добавим первые две строчки к нашей программе
from sys import *
setrecursionlimit(2000)
Где 2000 - необходимая для нашей задачи глубина рекурсии.
Кэш
Реализуем функцию, которая находит числа Фибоначчи.
def f(n):
if(n==0):
return 0
if(n==1 or n==2):
return 1
if(n>2):
return f(n-1)+f(n-2)
Допустим, что мы вызываем f(6). f(6)=f(5)+f(4), т.е. для того, чтобы знать f(6) нам нужно знать f(5) и f(4). f(5)=f(4)+f(3) и т.д. Изобразим процесс вызова в виде графа.
Количество ребер здесь соответствует количеству вызовов (в данном случае их 14). Можно заметить, что количество вызовов (и в целом размер дерева) можно было бы сократить, если бы мы запоминали значения для тех f(n) которые мы уже нашли. То есть пройдем по левой ветке до конца, и тогда значение f(3) и f(4) мы уже будем знать, и в других ветках рассчитывать их не станем, а просто возьмем уже посчитанные.
Тогда вызовов становится не 14, а 8 и программа считает всё значительно быстрее. Этот процесс называется кэшированием (уже посчитанные значения сохраняются в кэш и при необходимости мы к ним обращаемся экономя время на повторном расчете этих значений). При решении некоторых задач возникает необходимость воспользоваться кэшированием для оптимизации времени выполнения. В python кэширование реализовано с помощью специальной библиотеки и подключается следующим образом:
from functools import *
@lru_cache
def f(n):
...