КОДЕКС

Демистификация рекурсии

Упрощенная концепция ошеломляющей

О чем весь этот шум?

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

Ключевые термины, которые необходимо знать

  • Базовый вариант
  • Отношение повторения
  • Рекурсивное определение
  • Рекурсивный спуск
  • Рекурсивное восхождение

Базовый случай - это, по сути, простейшая форма проблемы. Нам нужен базовый случай в наших рекурсивных реализациях, чтобы функция не вызывала себя бесконечно.

Отношение повторения - это использование определения проблемы в терминах более простой версии самой себя.

Сочетание базового случая и отношения рекурсии дает нам рекурсивное определение. Рекурсивные реализации почти всегда исходят непосредственно из рекурсивного определения.

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

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

Объяснение рекурсии через факториал числа

На изображении выше вы можете увидеть, как каждый из ключевых терминов может быть связан с некоторой частью процесса вычисления / реализации факториала числа. Факториал числа может быть записан как число, умноженное на факториал числа минус один. Показывая процесс, 4! = 4 * 3 !, 3! = 3 * 2 !, и так далее, приводит к рекурсивному спуску. Один раз 0! был обнаружен, замена его на 1 позволяет нам начать вычисление факториала. Последовательное вычисление, которое является результатом завершения умножения каждой факторизации, приводит к рекурсивному восхождению. Факториал 0, равный 1, является нашим базовым случаем (простейшая форма проблемы). 4! равно 4 * (4 - 1)! это наше рекуррентное отношение (проблема определяется в терминах более простой версии самой себя). Более общее рекуррентное соотношение для факториала любого числа было бы n! = n * (n - 1) !. Для любой рекурсивной реализации мы всегда хотим начать с написания базового случая. Делая это, он гарантирует, что наша функция не будет выполнять рекурсию бесконечно (при условии, что наш базовый случай и отношение рекурсии верны). Как видно на изображении выше, базовый случай и отношение повторения, записанные вместе, образуют рекурсивное определение. Рекурсивное определение позволит нам получить реализацию для вычисления факториала числа.

Рекурсивная факториальная реализация

Альтернативная реализация

Примечание. Базовый случай и отношение повторения являются переменными. Их значения полностью зависят от проблемы, которую вы пытаетесь решить рекурсивно. Прежде чем пытаться рекурсивно решить любую проблему, вы должны определить правильный базовый случай и отношение повторения. Однако есть такая поговорка: «Любую проблему, которую можно решить рекурсивно, можно решить итеративно». Поэтому не пытайтесь все решать рекурсивно. Если что-то может быть решено итеративно, то решайте это итеративно (если рекурсия не дает более быстрых скоростей выполнения).

Базовое объяснение структуры данных линейного связного списка

Единственная причина, по которой я даже упоминаю линейные списки ссылок в статье о рекурсии, - это их связь с моим методом, помогающим понять, как работает рекурсия. На изображении выше показано, как линейный связанный список представлен в рисованном формате. Слово «список» - это указатель на первый узел в связанном списке. Указатель - это просто переменная, которая хранит адрес некоторого элемента в памяти. В этом случае список хранит адрес (в памяти) первого узла в списке. Каждый из ящиков называется узлами. Узел связанного списка состоит из информационного поля и текстового поля. Информационное поле может содержать любой элемент. Эти элементы могут включать в себя все, от целых чисел до строк и даже объектов. Следующее поле содержит адрес следующего узла в связанном списке. Мы говорим, что следующее поле «указывает» на следующий узел в списке.

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

Мой метод визуального наблюдения за работой рекурсии

Как я применил концепции, связанные с линейным связанным списком, для понимания рекурсии? На изображении выше вы можете увидеть, как каждый вызов функции факториала имеет свой собственный указатель. Идея состоит в том, чтобы думать о каждом вызове функции как о доступе к своей собственной реализации функции. Другими словами, каждый вызов функции «указывает» на свою собственную реализацию. Такое представление о рекурсии позволяет визуально увидеть рекурсивный спуск и рекурсивный подъем в действии. Следуя указателям (или стрелкам, если это помогает вам лучше понять), переходя от одной реализации функции к другой, вы выполняете рекурсивный спуск. Когда вы дойдете до последней реализации функции (когда n = 0), переход по указателям назад к каждому вызову функции выполняет рекурсивное восхождение и в конечном итоге вычисляет 4 !.

Примечание: я написал оператор else в одной строке (когда n = 1), чтобы сэкономить место. Это делает метод лучше или хуже. Если бы оператор else был написан в другой строке, это никак не повлияло бы на то, как метод должен работать.

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