Что такое глубина рекурсии

Максимальная глубина рекурсии в Python и как её увеличить

Рекурсия — это техника в программировании, при которой функция вызывает саму себя напрямую или косвенно. Она может быть очень полезной для решения определенных задач, но имеет свои ограничения. Одно из них — максимальная глубина рекурсии.

В Python предусмотрено ограничение на максимальную глубину рекурсии, чтобы предотвратить переполнение стека и последующий сбой программы. Это ограничение обычно установлено на достаточно высоком уровне (обычно порядка 1000), но иногда, для решения определенных задач, может потребоваться увеличить этот лимит.

def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print(factorial(2000))

В этом коде функция factorial рекурсивно вызывает сама себя для вычисления факториала числа. Но при попытке вычислить факториал числа больше 1000, получаем ошибку RecursionError: maximum recursion depth exceeded in comparison .

Чтобы увеличить максимальную глубину рекурсии, можно использовать функцию sys.setrecursionlimit(limit) . Эта функция устанавливает максимальную глубину рекурсии на указанное значение. Но стоит быть осторожным, увеличивая этот лимит, так как это может привести к переполнению стека и сбою программы.

import sys sys.setrecursionlimit(3000) print(factorial(2000)) # Теперь это работает

Таким образом, хотя увеличение максимальной глубины рекурсии может быть полезным, с ним следует обращаться с осторожностью. Более того, часто большие глубины рекурсии указывают на то, что задача, возможно, может быть решена более эффективным способом, не используя рекурсию.

Рекурсия. Рекурсивные подпрограммы.

По известному вам правилу доступности переменных (объектов), в теле подпрограммы доступны все переменные (объекты), объявленные в самой подпрограмме, а также переменные (объекты) объявленные во всех объемлющих блоках, в том числе и имя самой подпрограммы. Исключение составляет случай, когда переменная (объект) имеет такое-же имя как и переменная в объемлющем блоке и экранирует собой глобальную переменную.

Следствием правила о доступности переменных (объектов) является возможность вызова подпрограммой самой себя.

Процедуры и функции, производящие вызов «самих себя» называют рекурсивными.

Рекурсия. Рекурсивный алгоритм.

Рекурсией называется ситуация, когда какая-то подпрограмма прямо или через другие подпрограммы вызывает себя в качестве подпрограммы. Реализуемый при этом алгоритм называется рекурсивным.

В математике очень часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие. В арифметической прогрессии, например, каждый следующий член равен предыдущему, увеличенному на разность прогрессии:

Формулы, выражающие очередной член последовательности через один или несколько предыдущих членов, называют рекуррентными соотношениями.

Рассмотрим для примера функцию вычисления факториала n!. Как правило ее определяют как правило произведения первых n чисел натурального ряда

Такое произведение можно легко вычислить с помощью итеративных конструкций (итерация ― это повторение), например, оператор цикла For

Procedure TForm1.Button1Click(Sender: TObject);

n:=StrToInt(Edit1.Text); // Вводим n для вычисления n!

For i:=1 to n do fact:=Fact*i;

Label1.Caption:=’Факториал ‘ +IntToStr(n)+’! =’+IntToStr(fact);

Однако существует другое определение факториала, в котором n! выражается через предыдущий (n-1)!, т.е. используется рекуррентная формула:

для любого n>0 n!=n*( n -1)!

Наличие рекуррентного соотношения позволяет использовать рекурсию. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:

If i=0 then fact:=1

n := StrToInt ( n ); // Вводим n для вычисления n !

Label1.Caption:=’ Факториал ‘+IntToStr(n)+’! =’+IntToStr(fact(n));

Чтобы понять, как она работает, вспомним, что на время выполнения подпрограммы вызывающая подпрограмма приостанавливается, а в оперативной памяти выделяется место для локальных переменных и параметров, вызванной подпрограммы. Таким образом, при вызовах подпрограмм в оперативной памяти «накапливаются» приостановленные программы. При рекурсивных вызовах одной и той же функции fact происходит то же самое, т.е. при каждом новом вызове функции fact для ее локальных переменных и параметров выделяются новые ячейки памяти. по завершению работы функции эти ячейки удаляются.

Программы, в которых используются рекурсивные подпрограммы отличаются простотой, наглядностью и компактностью кода. Однако за эту простату приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных подпрограмм требует значительно большего размера оперативной памяти во время выполнения, чем нерекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров подпрограмм, которые передаются по значению, выделяются новые ячейки памяти в программном стеке.

В Delphi нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только хорошо понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальных объектов подпрограммы и все эти копии, соответствующие цепочки активизированных и не завершенных рекурсивных вызовов, существуют независимо друг от друга.

Для рассмотрения различных форм рекурсивных подпрограмм введем некоторые определения, имеющие отношение к рекурсии.

Максимальное число рекурсивных вызовов подпрограммы без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии.

Текущий уровень рекурсии.

Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

Формы рекурсивных подпрограмм.

В общем случае любая рекурсивная подпрограмма (для примера назовем ее Rec) включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова P.

Главное требование к рекурсивным подпрограммам.

Главное требование к рекурсивным подпрограммам заключается в том, что вызов рекурсивной подпрограммы должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается рекурсивный возврат из всех вызванных на данный момент копий рекурсивной подпрограммы.

Существует три разных формы рекурсивных подпрограмм:

1) Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске).

2) Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).

3) Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры.

Рассмотренная в начале рекурсивная функция fact, выполняет вычисление факториала на возврате. Рассмотрим более подробно действия этой функции при вычислении 5!, используя трассировку программы (запись значений переменных на различных этапах выполнения программы).

В качестве примера мы использовали рекурсивную функцию вычисления факториала натурального числа. Может показаться, что составить программу для вычисления n! используя прямую формулу значительно проще, чем составить программу на основе рекуррентного соотношения. Но в подавляющем большинстве случаев это не так. В качестве второго примера рассмотрим программу для вычисления члена последовательности Фибоначчи, для которого рекуррентное соотношение

для любого n>2 F(n)=F(n-1)+F(n-2)

выглядит значительно проще, чем прямая формула

используя которую составить программу практически невозможно. Приведем функцию, благодаря которой можно быстро рассчитать эти числа:

If (i=1) or (i=2) then fib:=1

Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой, например:

Procedure A (i : Byte);

Procedure В (j : Byte) ;

Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Чтобы такого рода вызовы стали возможны, вводится опережающее описание:

Procedure В (j : Byte); Forward;

Procedure A (i : Byte);

Как видим, опережающее описание заключается в том, что объявляется лишь заголовок процедуры в, а ее тело заменяется стандартной директивой Forward. Теперь в процедуре А можно использовать обращение к процедуре В ― ведь она уже описана, точнее, известны ее формальные параметры, и компилятор может правильным образом организовать ее вызов. Обратите внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.

Пример использования рекурсивной подпрограммы:

Задача: пара кроликов приносит раз в месяц приплод из двух крольчат (самца и самки), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько пар кроликов появится через год, если в начале года была одна пара кроликов и в течение года кролики не умирают, а их воспроизводство не заканчивается?

Procedure recursya(i:Int64; Var kol1:Int64; Var kol2:Int64);

kol1:=1; //первоначальное количество пар кроликов

kol2:=2; //количество пар кроликов через месяц

i:=i-1; // рекурсивный спуск

Procedure TForm1.Button1Click(Sender: TObject);

recursya(12,kol1,kol2); //12 — количество месяцев

1. Что такое рекурсия?

2. Какие соотношения называют рекуррентными?

3. В чем заключаются преимущества и недостатки в использовании рекурсивных подпрограмм по сравнению с нерекурсивными?

4. Что называется глубиной рекурсии?

5. Что называется текущим уровнем рекурсии?

6. Сформулируйте основные требования к рекурсивным подпрограммам.

7. Назовите формы рекурсивных подпрограмм.

8. Что называют рекурсивным спуском и возвратом?

Что такое глубина рекурсии

Скачай курс
в приложении

Перейти в приложение
Открыть мобильную версию сайта

© 2013 — 2023. Stepik

Наши условия использования и конфиденциальности

Public user contributions licensed under cc-wiki license with attribution required

Рекурсия — Python: Функции

В этом уроке мы узнаем, что такое рекурсия, зачем она нужна и чем отличается рекурсия в математике и в языках программирования. Еще мы разберем условие завершения рекурсии и обсудим, какие виды рекурсии существуют.

Что такое рекурсия

Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования используют этот подход.

Это работает и в Python. Обычно в определении функции можно использовать только определения, которые дали ранее. Но есть одно исключение — функция в своем теле может вызывать себя. Выглядит это так:

def factorial(n): if n  0: return 1 return n * factorial(n - 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py

Эта функция вычисляет факториал числа n через умножение числа на факториал числа n — 1 .

Условие завершения рекурсии

В примере выше используется условие, которое прекращает рекурсию. Если в этой функции убрать условие, которое проверяет аргумент на неотрицательность, то первый же вызов этой функции заставит программу зациклиться — функция продолжит вызывать себя постоянно.

В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:

• По рекурсивной — в этой ветке произойдет вызов себя
• По терминальной — закончит вычисление и вернет результат

Какой-то из аргументов рекурсивной функции должен обязательно убывать. В качестве убывания может быть:

• Уменьшение счетчика
• Отбрасывание головы списка при движении к его хвосту
• Вызов себя для части исходной структуры при обработке древовидных структур данных

Чтобы понять, что программа не зациклится, используют метод «пристального взгляда» и тесты. Особенно важно проверять срабатывание условия завершения рекурсии.

Переполнение стека

В большинстве программ, написанных на поддерживающих вызов функции языках, этот вызов устроен так: перед вызовом функции текущее место в программе запоминается в стеке. А когда функция возвращает результат, то соответствующий элемент стека отбрасывается.

Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.

В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, которая выделяется для стека при запуске программы, конечна и ограничена.

Если функция будет вызывать себя постоянно и не возвращать результат, то память в итоге закончится. Когда заканчивается память, выделенная для стека вызовов, стек переполняется.

В итоге мы не сможем посчитать факториал для достаточно больших чисел с помощью рекурсивной функции. Но сможем посчитать с помощью итеративной — написанной с использованием циклов и переменных.

Так выглядит переполнение стека при подсчете факториала:

factorial(1000) # Traceback (most recent call last): # File "", line 1, in # File "", line 4, in factorial # File "", line 4, in factorial # File "", line 4, in factorial # [Previous line repeated 995 more times] # File "", line 2, in factorial # RecursionError: maximum recursion depth exceeded in comparison 

Сообщение говорит, что превышена максимальная глубина рекурсии. Глубиной рекурсии называется количество последовательных вызовов себя без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.

Зачем нужна рекурсия

Некоторые алгоритмы реализуются проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными структурами данных — деревьями, «словарями словарей словарей» и подобными. При реализации таких алгоритмов нужно помнить, что память для стека конечна. При этом обычно конечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит.

Виды рекурсии

Рекурсии можно разделить на два вида по тому, как они себя вызывают:

• Прямая — когда функция вызывает себя
• Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую

Так же рекурсии можно разделить по количеству рекурсивных вызовов:

• Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с factorial . Уточним, что «один раз» — это не про общее количество вызовов функции в теле. Речь идет о количестве вызовов, результаты которых нужны для одного общего вычисления
• Каскадная — когда функция вызывает себя несколько раз

Рассмотрим подробнее линейную и каскадную рекурсию.

Пример линейной рекурсии

Если рекурсия в функции проверяет Гипотезу Коллатца , она считается линейной:

def collatz(n): if n == 1: return True if n % 2 == 0: return collatz(n // 2) return collatz(n * 3 + 1) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py

Здесь в теле функции есть два рекурсивных вызова, но в каждом заходе используется только один.

Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:

• Начало (голову)
• Остальную часть коллекции (хвост)

Дальше хвост также можно разложить на голову и новый хвост. И так до тех пор, пока не останется голова и пустой хвост:

 [1, [2, 3]] -> [1, [2, [3]]] -> [1, [2, [3, []]]] 

При рекурсивной обработке коллекции мы будем обходить коллекцию и дробить старый хвост на новую голову и новый хвост на каждой итерации. Так мы делаем до тех пор, пока не получим пустой хвост — то есть конец коллекции:

# Функция рекурсивно обходит список, суммируя числа из него def sum(array): # Мы можем использовать оператор упаковки для записи в хвост остальной части списка head, *tail = array if not tail: return head return head + sum(tail) 

Пример каскадной рекурсии

Если рекурсия в функции вычисляет очередное Число Фибоначчи , она называется каскадной:

def fibonacci(n): if n  2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) 

Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py

Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях: