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

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

Может, заглянем под капот?

Стек:

Одно из наиболее доступных объяснений стека, с которым я столкнулся, взято из Книги по языку программирования Rust.

И стек, и куча являются частями памяти, доступными вашему коду для использования во время выполнения, но они структурированы по-разному. Стек сохраняет значения в порядке их получения и удаляет значения в обратном порядке. Это называется последним пришел - первым ушел. Представьте себе стопку тарелок: когда вы добавляете больше тарелок, вы кладете их поверх стопки, а когда вам нужна тарелка, вы снимаете одну сверху. Добавление или удаление пластин посередине или снизу тоже не сработает! Добавление данных называется помещением в стек, а удаление данных называется выталкиванием из стека.

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

Методы, фреймы и стек:

В программе Ruby, когда вызывается метод, кадр попадает в стек (push). Этот фрейм по сути является экземпляром метода, содержащим локальные переменные, аргументы, которые были переданы методу, какому экземпляру он принадлежит, куда вернуться после его завершения, и указатель на сам метод. После того, как весь метод выполнен, фрейм снимается со стека (всплывает).

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

Если бы я добавил второй метод, который вызывается первым, это могло бы выглядеть примерно так:

Здесь вызывается grade_assignment и его кадр помещается в стек, в этом методе вызывается total_score, и его кадр также помещается в стек, в то время как grade_assignment приостанавливается и ожидает. После завершения total_score его кадр выскакивает из стека, и мы возвращаемся к grade_assignments, который нас ждал. Он заканчивается, а затем его фрейм также выскакивает из стека.

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

Рекурсия

Согласно Оксфордскому словарю:

рекурсия: (существительное) Повторное применение рекурсивной процедуры или определения.

Спасибо, очень полезно. Но если мы посмотрим на его корень, мы получим следующее:

повторяться: (глагол) Повторяться периодически или неоднократно.

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

Давайте сложим это вместе со стопкой, чтобы увидеть, как это выглядит.

Рекурсия зацикливания

Я думаю, что самый простой тип рекурсии - это когда метод выполняет свое дело, а последняя часть его команд снова обращается к себе.

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

Рекурсия цикла и стек

Давайте обратим внимание на то, как это выглядит в стеке. Это становится немного сложнее:

Здесь мы вызываем начальный say_good_morning, который вызывает себя снова и снова, пока не сработает оператор return. Каждый раз, когда say_good_morning вызывается изнутри say_good_moring, текущий кадр say_good_morning должен ждать, пока вызываемый say_good_morning он не выйдет из стека, чтобы попасть в свою конечную строку и выйти стек тоже.

Рекурсия Vortex

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

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

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

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

Давайте попробуем это с 3 студентами.

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

Давайте теперь посмотрим на ученика посередине.

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

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

Я призываю вас подумать, как эта серия вызовов методов повлияет, если мы добавим в комбинацию еще двух учеников.

Резюме

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

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

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