На прошлой неделе мы реализовали и обсудили сортировку вставками в Ruby. Мы видели, что сортировка вставками была довольно интуитивной с точки зрения человека, но с точки зрения алгоритмов сортировки она была не очень эффективной. На этой неделе мы не будем погружаться сразу в сортировку слиянием, а поговорим о рекурсии — шаблоне, который можно найти повсюду вокруг нас и который необходимо понять для реализации сортировки слиянием. Не позволяйте названию или тому, что вы, возможно, слышали о рекурсии в прошлом, напугать вас, на самом деле это не так сложно. На следующей неделе мы реализуем сортировку слиянием в Ruby, но для этого на этой неделе мы погрузимся в рекурсию.
Рекурсивный алгоритм — это просто алгоритм, который обращается к самому себе для решения проблемы постепенно упрощая шаги. Давайте рассмотрим простой рекурсивный алгоритм, который рекурсивно печатает «Hello World» n раз.
Давайте пройдемся по этому алгоритму построчно. Предполагая, что мы вызываем этот метод так, HelloWorldRecursive(3) . Вы увидите в строке 2 выше, что мы сначала проверяем, меньше ли n единицы. Этот критически важный шаг во всех рекурсивных алгоритмах называется базовым случаем. Это случай или иногда случаи, которые вызывают выход рекурсивного алгоритма. Без этой проверки мы бы бесконечно запускали этот алгоритм. В итоге закончилась память. Все рекурсивные алгоритмы должны иметь базовый вариант или, в некоторых случаях, более одного базового варианта.
Затем, начиная со строки 4, предполагая, что базовый случай не был запущен, мы начинаем выполнять некоторую рекурсивную работу. Во-первых, мы просто выводим Hello World на консоль, что достаточно просто. Далее идет рекурсия, обратите внимание на строку 6, мы вызываем метод, в котором уже находимся! Мы делаем это, уменьшая n на единицу. Это также критически важно. Если бы мы не уменьшили n, мы бы никогда не достигли нашего базового случая и застряли бы в бесконечном цикле.
В конечном счете, это очень надуманный пример, который можно было бы решить гораздо проще с помощью простого цикла. Тем не менее, он иллюстрирует две важные части, связанные с разработкой рекурсивного алгоритма.
- Рекурсивный алгоритм должен иметь базовый случай, который позволяет завершить алгоритм.
- Рекурсивный алгоритм должен каким-то образом манипулировать рассматриваемыми данными, чтобы в конечном итоге запустить базовый случай.
Без обоих вышеуказанных требований бесконечный цикл неизбежен, что, несомненно, нежелательно.
Будем надеяться, что этот дурацкий упрощенный пример помог объяснить основы рекурсии таким образом, что устранил любую путаницу, которая у вас могла возникнуть. Давайте немного закрепим это знание, попробовав решить задачу, которая на самом деле немного лучше поддается рекурсии, факториалам.
Что такое факториал, вы можете спросить, а можете и не спросить, если вы уже знаете, что такое факториал. Для тех из вас, кто не хочет, давайте быстро посмотрим. По сути, факториал числа n — это n, умноженное на все числа, меньшие n, вплоть до 1. Более формально, n! = n * (n-1) * (n-2) * … * 2 * 1. Например 4! = 4 * 3 * 2 * 1 = 24.
Возможно, вы уже видите рекурсивный шаблон. Мы можем решить 3! узнав, что такое 3 * 2! является. Тогда мы можем решить 2! узнав, что такое 2 * 1! является. Но подождите 1! равно 1. Ах, мы нашли наш базовый случай. Итак, давайте попробуем кодировать это.
Этот шаблон должен выглядеть очень знакомым с нашим рекурсивным алгоритмом Hello World выше. Мы начинаем с проверки нашего базового случая, если n == 1, то мы просто возвращаем 1, потому что мы знаем, что 1! это один. В противном случае мы рекурсивно вызываем наш факторный метод и спрашиваем его, что такое n * factorial( n — 1 ). Это удовлетворяет нашему второму требованию к рекурсивному алгоритму, изложенному выше. Удаляя 1 из n для каждого рекурсивного вызова factorial(), мы знаем, что в конечном итоге n станет равным 1, и наш рекурсивный алгоритм начнет возвращать эти результаты. Изображение ниже может помочь прояснить, как работают эти операторы возврата.
Обратите внимание, что приведенное выше изображение иллюстрирует алгоритм, который проверяет базовый случай n == 0, хотя результат тот же, поскольку 1 * 1 = 1.
Надеюсь, рекурсия теперь немного менее загадочна. Это было очень простое исследование рекурсии, предназначенное в основном для веб-разработчиков и других менее математических групп программистов. Рекурсия — это простая идея, которая усложняется тем фактом, что она не очень интуитивно понятна нам, людям. Рекурсивные паттерны часто не бросаются в глаза, как это делают некоторые другие паттерны. При этом рекурсия присутствует в информатике повсюду, от сортировки слиянием до бинарных деревьев и так далее. Благодаря нашим новым знаниям в области рекурсии мы сможем заняться сортировкой слиянием на следующей неделе. Увидимся позже.
