🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции

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

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

Стек – это структура данных LIFO (last in, first out): информация последовательно добавляется в «стопку» , каждый новый объект помещается поверх предыдущего, а извлекаются объекты в обратном порядке, – начиная с верхнего. Работу стека отлично иллюстрирует добавление данных в список с помощью append и извлечение информации посредством pop:

stack = []
for i in range(1, 11):
    stack.append(f'{i}-й элемент')
    print(f'+ {i}-й элемент добавлен')
    for i in stack:
        print(i, end=" ")
print('\n')    
for i in range(len(stack)):
    print('В стеке: ', end=" ")
    for i in stack:
        print(i, end=" ")
    print(f'\n{stack.pop()} удален из стека')

Вывод:

+ 1-й элемент добавлен
1-й элемент + 2-й элемент добавлен
1-й элемент 2-й элемент + 3-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент + 4-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент + 5-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент + 6-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент + 7-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент + 8-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент + 9-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент + 10-й элемент добавлен
1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 10-й элемент 

В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 10-й элемент 
10-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 9-й элемент 
9-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 8-й элемент 
8-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 7-й элемент 
7-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 6-й элемент 
6-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 5-й элемент 
5-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 4-й элемент 
4-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 3-й элемент 
3-й элемент удален из стека
В стеке:  1-й элемент 2-й элемент 
2-й элемент удален из стека
В стеке:  1-й элемент 
1-й элемент удален из стека

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

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

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

Программисту не нужно беспокоиться о работе стека вызовов – созданием фреймов и управлением стеком занимается интерпретатор. Однако понимание принципа работы стека вызовов значительно упрощает создание рекурсивных функций. Неверное же использование рекурсии приводит к переполнению стека (stack overflow). Популярный сайт StackOverflow назван как раз в честь этой ошибки.

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

def recursive():
    recursive()

recursive()

Интерпретатор Python автоматически отслеживает переполнение стека и после 1000 бесплодных вызовов завершает работу подобных функций с ошибкой:

shortest()
RecursionError: maximum recursion depth exceeded

При желании лимит на глубину рекурсии можно увеличить, но сделать его бесконечным, разумеется, нельзя – даже самый внушительный объем оперативной памяти в итоге окажется переполненным:

from sys import getrecursionlimit
from sys import setrecursionlimit
print(getrecursionlimit()) # выводит лимит по умолчанию
setrecursionlimit(2000) # увеличивает лимит до 2000 вызовов
print(getrecursionlimit())# выводит новый лимит

#Вывод:
1000
2000

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

1. Граничный, при котором функция завершает работу и возвращает данные в основную программу.
   
2. Рекурсивный, при котором функция продолжает вызывать себя.
   

Вот пример простейшей рекурсивной функции, в которой учтены оба случая:

def greetings(st):
     print(st)
     if len(st) == 0:  # Граничный случай
         return             
     else:       # Рекурсивный случай
         greetings(st[:-1])   

greetings('Hello, world!')

Вызовы функции прекращаются, когда длина выводимой подстроки достигает 0:

Hello, world!
Hello, world
Hello, worl
Hello, wor
Hello, wo
Hello, w
Hello, 
Hello,
Hello
Hell
Hel
He
H

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

def greetings(st):
    print(st)
    if len(st) > 0:  
        greetings(st[:-1])   

greetings('Hello world!')

И в первом, и во втором варианте рекурсивный случай многократно передает в функцию greetings() подстроку, длина которой уменьшается с каждым вызовом, пока не станет равной 0.

Отлично! Вы поняли самую суть рекурсии.

Теперь вы знаете, как работает стек вызовов, и умеете писать рекурсивные функции с базовым случаем, чтобы избежать ошибки RecursionError. У вас есть вся необходимая теория, чтобы начать.

Но знать, как написать рекурсию, — это лишь первый шаг. Гораздо важнее понимать, когда её стоит применять и как делать это эффективно. В полной версии урока вы узнаете:

• Почему рекурсия почти всегда медленнее обычных циклов (с наглядным тестом производительности).
• Как ускорить рекурсивные функции в сотни раз с помощью техники мемоизации и декоратора @lru_cache.
• Как решить 10 практических задач двумя способами — рекурсивным и итеративным, чтобы на деле оценить их плюсы и минусы.