Глубина рекурсии

Напишем функцию, которая ищет 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):
    ...
Last modified: Friday, 8 August 2025, 1:04 PM