Рекурсия и стек

Рекурсия

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

1. Сложить все коробки в кучу или просто обнаружить их все которые существуют на виду;
2. Открыть какую нибудь закрытую коробку;
3. Если внутри лежит коробка, добавить её в кучу для последующего вскрытия и иска;
4. Если внутри лежит ключ, поиск закончен!
5. Повторить пункт 2.

Есть также альтернативное решение:

1. Просмотреть содержимое коробки;
2. Если найдена внутри ещё коробка, выполнить пункт 1;
3. Если нашли ключ, то поиск закончен!

Какое решение наиболее простое? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить её содержимое. Напишем условный или псевдокод на python:

def look_key(box):
  pile = box.make_to_look()
  while pile is not empty:
    bx = pile.give_box()
    for item in bx:
      if item.is_a_box():
        pile.append(item)
      elif item.is_a_key():
        print("Найден ключ!")

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

def look_key(box):
  for item in box:
    if item.is_a_box():
      look_key(item)  # Здесь рекурсия!
    elif item.is_a_key():
      print("Найден ключ!")

Оба решения делают одно и тоже. При этом второе решение короче и когда вам известен такой способ как рекурсия, решение это становится более понятным. Применение рекурсии не ускоряет работу программы. Более того, решение циклами и с помощью динамического программирование(о нём в другой статье) иногда работает даже быстрее. Мне нравится одна фраза на эту тему: "Рекурсия может ускорить работу программиста, циклы могут ускорить работу программы. Выбирайте что вам нужнее в вашей ситуации!" Рекурсия используется во многих задачах, поэтому важно понимать её концепцию и применимость.

Базовый и рекурсивный случай

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

def ctdown(i):
  print(i)
  ctdown(i-1)

ctdown(3)

Запустив такой код возникает проблема: эта функция будет выполнять бесконечно! Чтобы прервать выполнение, нужно закрыть консоль или нажать Ctrl+C. Когда вы пишете рекурсивную функцию, в ней необходимо предусмотреть момент прерывания рекурсии. Поэтому каждая правильно написанная рекурсивная функция состоит из двух частей: базового и рекурсивного случая. В рекурсивном случае функция вызывает сама себя. В базовом случае функция себя не вызывает, а наоборот предотвращает вызов и тем самым "зацикливание". Добавим базовый случай в функцию ctdown:

def ctdown(i):
  print(i)
  if i <= i:
    return
  ctdown(i-1)

ctdown(3)

Теперь функция работает как было задумано.

Стек

Рассмотрим такое понятие как стек вызовов. Концепция стека вызовов важно понимать в программировании и особенно при использовании рекурсии. Предположим вы устраиваете вечеринку и составляете список задач записывая все дела на листках. Задачи, представим что это элементы некоторого единого списка, но будут вместе выглядеть как стопка листков. Новые (вставленные) элементы добавляются всегда в начало списка, то есть наверх стопки с листочками. Читается всегда только верхний элемент, и он же исключается из списка(из стопки). Таким образом, список задач поддерживает всего два действия: занесение(вставка или добавление) и извлечение (чтение и удаление). Посмотрим, как работает такой список задач реализованный через стек:

1. Задача извлекается из стека(из стопки);
2. Читается и выполняется;
3. Либо пункт 1, 2 повторяются снова(только если стек не будет пустым) либо добавляется новая задача или задачи в стек. Программисты новички с самого начала программирования уже пользуются стеком даже не подозревая об этом!

Стек вызовов

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

def greetings(name):
  print("Привет, " + name + "!")
  greet(name)
  print("Дальше будет пока...")
  goodbye()

Эта функция приветствует вас, после чего вызывает две другие функции. Например:

def greet(name):
  print("Как твои дела, " + name + "?")

def goodbye(name):
  print("Хорошо, пока!")

Разберемся, что происходит при вызове функции. Предположим, в программе используется вызов greetings("Иван"). Сначала ваш компьютер выделяет блок памяти вызова функции. Затем эта память используется. Переменной name присваивается значение "Иван"(оно также должно быть сохранено в памяти). Каждый раз, когда вы вызываете функцию, компьютер сохраняет в памяти значения всех переменных для вызова. Далее выводится приветствие: Привет, Иван!, после чего следует второй вызов greet("Иван"). И снова компьютер выделяет блок памяти для вызова функции. Далее ваш компьютер объединяет эти блоки в стек. Второй блок в стеке с вызовом функции greet создаётся над первым блоком с вызовом функции greetings. Вы видите сообщение Как твои дела, Иван?, после чего возвращается управление из вызова функции. Когда это происходит, блок на вершине стека извлекается из него(извлекается вызов функции greet). Теперь верхний блок в стеке относится к функции greetings; это означает, что вы вернулись к функции greetings. При вызове функции greet функция greetings ещё не была завершена. Получается, когда происходит вызов функции из другой функции, вызывающая функция приостанавливается в частично завершенном состоянии. Все значения переменных этой функции остаются в памяти. А когда выполнение функции greet будет завершено, происходит возврат к функции greetings в то же место, где выполнение её прервалось. И наконец, далее сначала выводится сообщение Дальше будет пока..., после чего вызывается функция goodbye. Блок для функции goodbye добавляется на вершину стека. И напоследок выводится сообщение Хорошо, пока! с выходом из вызова функции. Управление снова возвращается функции greet. Делать в программе больше нечего, так что управление возвращается и из функции greetings. Такой стек в котором сохранялись вызовы разных функций называется стеком вызовов. Посмотрим, как работает стек вызовов с рекурсивными функциями.

Стек вызовов с рекурсией

В рекурсивной функции тоже используются стек вызовов! Самое просто это посмотреть на примере рекурсивной функции вычисления факториала. На Python запишем её так:

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

Вызов функции factorial(5) вычисляет факториал 5! и определяется следующим образом: 5! = 5 * 4 * 3 * 2 * 1. То же самое соответствует вызов функции factorial(4) 4! = 4 * 3 * 2 * 1. Проанализируем этот вызов:

Пошаговое формирование стека

1. Вызов factorial(4)
   • Создаётся фрейм в стеке: factorial(4)
   • Условие n == 1 не выполнено → вызов factorial(3)
2. Вызов factorial(3)
   • Новый фрейм: factorial(3) (стек: factorial(4) → factorial(3))
   • Условие n == 1 не выполнено → вызов factorial(2)
3. Вызов factorial(2)
   • Новый фрейм: factorial(2) (стек: factorial(4) → factorial(3) → factorial(2))
   • Условие n == 1 не выполнено → вызов factorial(1)
4. Вызов factorial(1)
   • Новый фрейм: factorial(1) (стек: factorial(4) → factorial(3) → factorial(2) → factorial(1))
   • Условие n == 1 выполнено → возврат 1
5. Разворачивание стека (возвраты)
   • factorial(1) возвращает 1 → factorial(2) вычисляет 2 * 1 = 2 → возвращает 2
   • factorial(3) вычисляет 3 * 2 = 6 → возвращает 6
   • factorial(4) вычисляет 4 * 6 = 24 → возвращает 24

Графическая визуализация стека (вертикально, сверху — последний вызов)

[ factorial(1) ]  ← Базовый случай (возврат 1)
[ factorial(2) ]  ← Вычисляет 2 * 1 = 2
[ factorial(3) ]  ← Вычисляет 3 * 2 = 6
[ factorial(4) ]  ← Вычисляет 4 * 6 = 24

Текстовая трассировка (по шагам)

1. factorial(4) → вызывает factorial(3)
2. factorial(3) → вызывает factorial(2)
3. factorial(2) → вызывает factorial(1)
4. factorial(1) → возвращает 1
5. factorial(2) → возвращает 2 * 1 = 2
6. factorial(3) → возвращает 3 * 2 = 6
7. factorial(4) → возвращает 4 * 6 = 24

Схема в виде дерева вызовов

factorial(4)
├── factorial(3)
│   ├── factorial(2)
│   │   └── factorial(1) → 1
│   └── 2 * 1 = 2
└── 3 * 2 = 6
└── 4 * 6 = 24

Ключевые моменты

• Стек растёт при рекурсивных вызовах (каждый новый фрейм добавляется сверху).
• Стек сокращается при возвратах (фреймы удаляются по порядку LIFO — «последний вошёл, первый вышел»).
• Базовый случай (n == 1) останавливает рекурсию и запускает разворачивание стека.

Стек вызовов наглядно показывает, как рекурсия «погружается» в вызовы, а затем «поднимается» с результатами. Стек играет важнейшую роль в рекурсии. Здесь важно, что каждый вызов функции создаёт собственную копию переменной n. Обратиться к переменной n, принадлежащей другой функции(или её вызову) – невозможно! Стек в данном случае особенно удобен, потому что вам не нужно отслеживать значения переменной каждый раз самостоятельно – стек делает это за вас!

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

1. Переписать код с использованием цикла;
2. Иногда можно воспользоваться так называемой "хвостовой рекурсией". Это непростая тема, которая вдобавок поддерживается далеко не во всех языках программирования.

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.