Представьте, что ребенку на день рождения подарили подарок, завернутый в коробки внутри коробок. Чтобы получить подарок, как поступил бы нормальный человек, вы не стали бы сразу резко разрезать упаковку пополам, потому что вы можете сломать то, что внутри. Итак, ребенок сдерживает свое волнение, когда он осторожно распаковывает каждую большую коробку с меньшими коробками, пока не добирается до ожидаемого подарка - русской чайной куклы или «матрешки», которая по сути является куклой внутри куклы. Затем мать призвала его смотреть дальше, сказав: «Хорошие вещи приходят к тем, кто упорствует». Сразу же мальчик разложил куклы, пока не обнаружил, что держит в руках главный подарок - ключ от своего нового игрового домика, который по сути представляет собой дом в доме.

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

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

Информатика и рекурсия

Одним из наиболее распространенных примеров, используемых для демонстрации рекурсии, является вычисление факториала положительного числа n (обозначается как n!), которое может быть выражается так: n! = n * (n-1) * (n-2) * ... * 1. Он выполняется путем произведения всех чисел между заданным числом n и 1 (включительно). Возьмем в качестве примеров 2!, 3! и 4!:

2! = 2 * 1 = 2

3! = 3 * 2 * 1 = 6

4! = 4 * 3 * 2 * 1 = 24

Если вы внимательно посмотрите, то заметите, что 3! совпадает с 3 * 2!, а 4! равно 4 * 3! или 4 * 3 * 2!. Вы видите, как в этом примере происходит рекурсия? При вычислении факториала мы преобразуем его в факториалы меньшего размера, пока не сможем решить его напрямую. Функция в исходном коде ниже соответствует рекурсивному решению факторной проблемы.

Мы уже знаем, что факториалы включают только положительные числа, поэтому мы позволяем строке 2 нашего кода позаботиться об этом случае. Если мы забудем эту строку при отрицательном вводе, выполнение нашего кода будет продолжаться бесконечно или до тех пор, пока программа не выйдет из строя; и вы бы не хотели, чтобы это произошло. Кроме того, 0! равно 1 - это универсальный факт, и вы ничего не можете сделать, чтобы его изменить. Итак, мы позволим строке 3 справиться с этим. Строка 4 - это место, где происходит рекурсия, потому что она вызывает вызов той же функции, в которой находится, - следовательно, рекурсивный вызов.

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

Анатомия рекурсивной функции

Функция может быть рекурсивной, если она интуитивно вычислима, эффективно вычислима, определяется механическим процессом или заданный алгоритмом , как заявил Роберт Соар (1996) в своей книге Вычислимость и рекурсия . Правильно написанные рекурсивные функции имеют следующие части / особенности:

  • Условия прекращения

Здесь будут обрабатываться плохие входные данные. В нашем исходном коде функции факториала выше строка 2 (if (iNum < 0) return; ) является условием завершения, потому что она улавливает все отрицательные числа, что, как мы все знаем, не допускает факториала. Он немедленно останавливает рекурсивную функцию.

  • Базовый вариант или Случай остановки

Помните, что все хорошо написанные рекурсивные функции всегда доходят до точки, на которой рекурсивный процесс заканчивается. Вот тут-то и срабатывает базовый случай. Он останавливает или останавливает последующие рекурсивные вызовы, при условии, что на входе нет плохих данных, в противном случае он попадает в условие завершения. В нашей факториальной функции строка 3 (else if (iNum === 0) return 1;) является нашим базовым случаем. Как вы можете видеть, он возвращает четко определенное значение, равное 1. Его также можно назвать целью рекурсивной функции, потому что в нашем примере вы будете знать, что закончили решение для факториала, если вы достигли 0. Более того, вы можете указать более одного базового случая в зависимости от того, что требует проблема. Суть базовых случаев заключается в том, что вы должны явно представлять их в своем коде и тщательно продумывать их написание, иначе вы не увидите того вывода, который вы хотите, чтобы выполняла ваша функция.

  • Рекурсивный регистр или Общий регистр

Это то, что происходит в большинстве случаев, поскольку именно здесь функция вызывает сама себя. В нашем примере рекурсивный вызов происходит в строке 4 (return iNum * factorial(iNum - 1);). Он возвращает рекурсивно определенное значение. Это означает, что он возвращает вычисленное значение, полученное при последующем вызове. Кроме того, вам необходимо изменить параметр, который вы передаете в свой рекурсивный вызов (iNum - 1), чтобы уменьшить размер проблемы, которую должен решить следующий вызов. В противном случае ваш код попадет в бесконечный цикл.

Другие примеры

Вы можете посмотреть другие примеры и упражнения по рекурсии здесь:

Плюсы и минусы рекурсии

Преимущества рекурсии следующие:

  1. Аккуратный и элегантный
    Рекурсивные функции легче читать. Обычно он не должен объявлять локальные переменные так же часто, как его итеративный аналог. Beau Carnes (2017) заявил, что как только вы это поймете, это станет понятнее для чтения. Рекурсивные функции обычно имеют более короткий код, чем их итеративный подход. Итерация почти всегда является более очевидным решением каждой проблемы, но иногда предпочтительнее простота рекурсии.
  2. Пониженная сложность проблемы
    Рекурсия решает сложные проблемы, создавая более мелкие экземпляры проблемы.
  3. Интуиция
    Рекурсивные процедуры дали Тони Хоару интуицию при написании своего знаменитого алгоритма быстрой сортировки. Практикуя рекурсивное мышление, вы можете получить то же понимание, которое Хоар имел при написании своего элегантного алгоритма.
  4. Сложно
    Может показаться, что это недостаток, но если вы подумаете о нем положительно, вы поймете, какую пользу это может принести вам как разработчику. По мнению Максима Корецкого (2017), рекурсия - одна из важнейших идей в информатике. Итак, изучение этого - всего лишь правильный способ расширить набор инструментов, которые вы можете использовать, и изменить то, как вы смотрите на код. Это продвинутая техника, требующая навыков и немного чутья, которые вы также можете использовать в других областях программирования.

Недостатки рекурсии следующие:

  1. Переполнение стека вызовов
    Для перевода рекурсивных процедур требуется стек. Могут быть случаи, когда вы выполняете свою рекурсивную функцию и сталкиваетесь с ошибками, указывающими, что размер стека превышен. Это происходит из-за того, что вызывается слишком много рекурсивных методов, каждый со своим фреймом, занимающим стек. Когда эти кадры продолжают помещаться в верхнюю часть стека вызовов, выполнение каким-то образом достигает точки, когда общий размер кадров превышает размер стека, что приводит к переполнению стека.
  2. Неэффективность
    Рекурсивные функции выполняются относительно дольше и медленнее, чем их итерационные аналоги. Члены группы Алгол-60 Кристофер Стрейчи и Клаус Самельсон утверждали, что рекурсивные процедуры приводят к неэффективным объектным программам. Хотя эффективность выполнения программы зависит от общей стоимости проекта, Самельсон предложил избегать рекурсивных процедур для минимизации финансовых затрат. Эдсгер Джикстра, главный сторонник рекурсии, признал, что его подход к рекурсивному программированию привел к неэффективному машинному коду, хотя он также защищал, что эти проблемы эффективности будут решены или станут незначительными в будущем.
  3. Никакого повышения производительности
    Вы не получите никакого повышения производительности при реализации рекурсии, потому что итерация обычно имеет меньшую временную сложность при ее выполнении.

Рекурсия против итерации

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

Давайте рассмотрим рекурсивную факториальную функцию, объясненную ранее.

Ниже представлена ​​итерационная версия факториальной функции:

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

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

Когда следует использовать рекурсию

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

Используйте рекурсию, если:

Используйте итерацию, если:

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

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

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

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

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

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

использованная литература