Рекурсией называется ситуация, когда функция вызывает сама себя
Простой пример рекурсии в Python
Наша задача - написать функцию, которая принимает в качестве параметра положительное число, а затем возвращает сумму всех чисел, меньших заданного числа.
Решение с помощью цикла.
def suma_for(сol):
suma = 0
for i in range(сol + 1):
suma += i
return сol
Решение c рекурсией в Python.
def demo_recurs(col):
if col == 0: return 0
return col + demo_recurs(col - 1)
Первое решение, не требует комментариев. Оно понятно, если вы немного знакомы с Питоном.
Но рекурсивное решение намного интереснее.
Функция возвращает заданное число плюс то, что она возвращает, если мы уменьшаем число на единицу, плюс то, что она возвращает, если мы снова уменьшаем число на 1.
Если число достигает 0, функция больше не выполняется.
Если мы вызовем нашу функцию со значением 3 - demo_recurs (3), то будет произведен следующий расчет:
- 3 + demo_recurs (2), т.е.
- 3 + 2 + demo_recurs (1), то есть
- 3 + 2 + 1 + demo_recurs (0), что является
- 3 + 2 + 1 + 0
В результате получаем 6
Когда используется рекурсия
По сути, мы можем заменить любой цикл рекурсивными функциями. Но мы также можем заменить любую рекурсивную функцию циклами.
Гораздо труднее представить себе, как работает рекурсия, и нужно немного привыкнуть, чтобы начать думать рекурсивными функциями, а не циклами. Многие программисты никогда ими не пользуются и не нуждаются в них.
ОДНАКО иногда проблему намного проще решить с помощью рекурсии. Особенно, если мы можем легко разбить его на более мелкие, одинаковые проблемы. Как в примере выше. Цикл по очереди подсчитывал сумму. Но рекурсия разбила проблему на более мелкие. В конце концов, она просто сложила все результаты.
Дерево, нарисованное рекурсивной функцией
Давайте посмотрим на простое дерево, созданное на Python Turtle.
Если мы присмотримся к нему поближе, он состоит из повторяющихся элементов.
- Линия нарисована
- В конце линии есть левая и правая ветвь, нарисованы линии и снова левая и правая ветви.
- Рисование заканчивается после седьмого элемента
Это очень просто сделать с помощью рекурсии:
import turtle
t = turtle.Turtle()
t.speed(-1)
t.setheading(90)
t.penup()
t.goto(0,-200)
t.pendown()
def vet(t, len):
if len == 0: return
nt = t.clone()
nt.forward(50)
nt.left(20)
vet(nt,len-1)
nt.right(40)
vet(nt,len-1)
vet(t, 7)
window = turtle.Screen()
window.exitonclick()
Как это работает.
- Определяем функцию ветвления
- Задача функции простая. Рисует ветку длиной 50 метров
- Затем она переворачивает "черепаху" влево на 20 градусов и вызывает себя, чтобы провести линию влево.
- Затем она поворачивает "черепаху" вправо на 40 градусов и вызывает себя, чтобы провести линию вправо.
- В качестве параметров у нас есть передаваемая "черепаха" и длина нарисованного дерева.
- Когда длина достигает 0, функция не выполняется
Можно сказать, что мы имеем дело с невероятно ленивой функцией. все, что он делает, - это рисует одну ветку, а другие функции рисуют остальные.
И в этом, помимо прочего, прелесть рекурсии.
Подсчет файлов на диске
Еще одна интересная проблема - подсчет количества файлов на диске.
В основном каталоге у нас есть x файлов и y каталогов. Мы, конечно, можем написать функцию, которая использует цикл для подсчета всего, но насколько это проще с рекурсией?
Просто напишите функцию, которая считает файлы, и когда она встречает каталог, она вызывает себя с именем этого каталога.
То же самое и в случае парсинга веб-страниц.
Предоставляем URL-адрес, функция загружает содержимое страницы. В тот момент, когда он встречает другой URL, она запускается с новым URL.
Заключение
Одни ненавидят это, другие любят.
Есть языки программирования, которые вообще не имеют циклов, только рекурсивные функции, такие как Haskell.
Ну и наконец: чтобы понять рекурсию, вы должны понять рекурсию.
---
Подписывайтесь на канал, впереди еще больше полезных статей по Python https://zen.yandex.ru/id/5f56875a664c2c1f0b8dc68a
Статья была полезной - поставьте палец вверх :-)