Продвинутые концепции рекурсии, которые должен знать каждый эффективный программист
Один из самых мощных и полезных подходов к кодированию
Рекурсия - один из самых мощных подходов к программированию. Он занимает одно из первых мест в списке полезных инструментов в арсенале программистов, поскольку позволяет решать чрезвычайно сложные задачи с помощью шокирующе небольшого количества кода. Однако часто концепция рекурсии может быть сложной для понимания, поскольку требует нестандартного представления о том, как обрабатываются команды.
Эта статья начнется с простых примеров и постепенно перейдет к более сложным, сопровождаемым обширными диаграммами:
- Рекурсивный способ мышления
- Повторяющиеся отношения
- Мемоизация
- Стратегия Divide & Conquer
Рекурсия - это подход к решению проблем, при котором функция вызывает себя в пределах определения функции. Каждая рекурсивная реализация должна иметь два элемента:
- Базовый вариант или случаи, которые являются завершающими случаями, в которых ответ не ищется дальше с дополнительной рекурсией.
- Набор правил (отношение рекурсии), которые сводят другие случаи к базовому, инициируя еще один раунд рекурсии.
Например, давайте рассмотрим задачу печати обратной стороны строки. Результатом ввода «hello» должно быть «olleh». Итерационный метод решения этой задачи заключается в использовании цикла for и распечатке каждого символа от последнего индекса до первого.
Рекурсивный метод будет первым, чтобы создать функцию reverseString, которая принимает строку в качестве параметра. Если длина ввода не равна 0 - это будет базовый или завершающий регистр - мы печатаем последнюю букву и инициируем другой экземпляр reverseString в текущей строке, исключая последний последний (поскольку он был только что напечатан).
Обратите внимание: поскольку функция вызывается внутри себя, она сама создает цикл for. Кроме того, наличие оператора if перед вызовом другого экземпляра функции обязательно - в противном случае будет выдано RecursionError или RuntimeError, потому что сценарий не видит конца бесконечному циклу. Это похоже на бесконечный цикл while True.
Давайте посмотрим, как эта рекурсивная функция действует на "hello":
Повторение более сложных проблем может быть сложной задачей, потому что определение двух его компонентов - отношения повторения, отношения между результатом проблемы и результатом ее подзадач; и базовый случай, случай, который можно вычислить напрямую, без каких-либо рекурсивных вызовов. Иногда базовые случаи называют «нижними случаями», поскольку это случаи, в которых проблема была сведена к минимальному масштабу.
Рассмотрим, например, треугольник Паскаля, в котором каждое число представляет собой сумму двух вышележащих чисел с единицами по сторонам треугольника. Как можно использовать рекурсию, чтобы найти значение любого значения в точке (i, j)? Что такое рекуррентное отношение и базовый / завершающий случай?
Рекуррентное соотношение может быть выражено следующим уравнением:
Это очевидно, если посмотреть на график треугольника. Что еще лучше в этой формуле, так это то, что если мы продолжим использовать ее для разбиения любого местоположения (i, j) как суммы двух других местоположений, это неизбежно приведет к базовому случаю - 1. Паскаль. треугольник начинается с единиц, а из суммы единиц возникает целый сложный узор.
Как мы могли это реализовать?
Для начала давайте найдем набор правил, чтобы определить, когда соблюден базовый вариант - значение ячейки равно 1. Обратите внимание, что единицы появляются при двух условиях: либо они находятся в первом столбце (j = 0), либо находятся по диагонали (i = j).
Теперь реализовать просто. Если условия базового случая соблюдены, мы возвращаем базовое значение (1). В противном случае мы продолжаем уменьшать проблему до тех пор, пока не достигнем базового случая, на который, как мы определили, неизбежно будут разбиты любые входные данные.
К настоящему времени вы уже должны были представить себе красоту рекурсии. Здесь мы, по сути, создаем саморазвивающееся дерево в пяти строках кода (это может быть даже три строки, если вы хотите его сократить). Когда мы дважды вызываем функцию pascal, мы запускаем две ветки поиска, каждая из которых инициирует еще две, предполагая, что они не достигли базового варианта.
Это может быть немного волшебно и сбивать с толку, как рекурсия работает так эффективно. Давайте разберемся, как работает рекурсивный алгоритм на примере.
(4, 2) разбивается на (3, 1) и (3, 2), которые являются двумя числами над ним, в соответствии с нашим рекуррентным соотношением. Обратите внимание, что алгоритм на самом деле не знает, что значения этих ячеек равны 3, он просто отмечает их расположение. Мы не знаем и не заботимся о какой-либо ценности, если она не удовлетворяет нашим базовым условиям. Из наших базовых случаев (1) мы можем вычислить другие небазовые местоположения, но сначала должны быть найдены все базовые случаи.
Согласно нашему рекуррентному отношению, случаи итеративно разбиваются до тех пор, пока не будет выполнен базовый вариант (j = 0 или i = j). Поскольку мы знаем значения этих базовых случаев (1), мы можем заполнить другие значения в зависимости от базового случая.
Это, конечно, чрезвычайно подробное представление о том, как работает рекурсивный алгоритм - возможно, даже чересчур. На самом деле ни один из этих трех шагов не нужно программировать; они выполняются автоматически скриптом. Все, что вам нужно сделать с точки зрения реализации, - это вызвать функцию внутри самой себя и убедиться, что в некоторых точках она должна завершаться в базовом случае.
Когда мы вызываем return pascal(i-1, j) + pascal(i-1, j-1), мы рассматриваем возврат не как процесс, а как число. Поскольку pascal(i-1, j) инициирует свои собственные процессы ветвления, но в конце вернет другое число (например, 3), полезно думать о нем как о втором, а не о первом, что может вызвать ненужные сложности и головокружение.
Можно указать на некоторую неэффективность этого рекурсивного алгоритма. В конце концов, «6» разбивается на «3», которые имеют идентичную разбивку (с точки зрения стоимости), но наивно вычисляются дважды. Это обычное явление в рекурсии, когда базовые случаи для одного случая уже вычислены, но вычисляются заново. Чтобы справиться с этим, мы используем мемоизацию.
Возьмем, к примеру, последовательность Фибоначчи, в которой первые два числа равны 0 и 1, а следующее число представляет собой сумму двух перед ним. Исходя из наших предыдущих знаний, мы понимаем, что базовыми случаями являются 0 и 1, а нашим рекуррентным отношением является v (i) = v ( i -2) + v (i -1). Таким образом, мы можем построить простую рекурсивную функцию, чтобы найти значение последовательности Фибоначчи по любому индексу i, начиная с 0.
Обратите внимание: хотя это умное приложение рекурсии, оно ужасно неэффективно. 8 разбивается на 3 и 5, а в свою очередь 5 разбивается на 3 и 2. Мы вычисляем все с нуля и строим полное дерево поиска с множеством дубликатов.
С мемоизацией мы можем решить эту проблему, создав кеш. Это может быть реализовано с помощью словаря и хранит значения, которые мы видели раньше. Например, когда индекс 6 (значение 8) разбивается на индекс 4 и индекс 5 (значение 3 и 5), мы можем сохранить значение индекса 4 в кеше. Когда индекс 5 рассчитывается как индекс 3 плюс индекс 4, мы можем извлечь индекс 4 из кеша вместо его повторного вычисления, построив еще одно обширное дерево до базовых случаев.
Чтобы добавить мемоизацию к нашей функции, мы добавляем две функциональные возможности: во-первых, если текущий индекс был сохранен в нашем кеше, мы просто возвращаем сохраненное значение; во-вторых, прежде чем мы продолжим уменьшать значение, мы добавляем это значение в кеш, чтобы можно было ускорить дальнейшие операции. Обратите внимание, что кеш должен быть глобальной переменной или переменной, которую можно извлекать и изменять независимо от области действия, в которой вызывается команда.
Благодаря простому добавлению мемоизации наша рекурсивная функция стала намного быстрее и мощнее, чем когда-либо прежде.
Рекурсия занимает центральное место во множестве самых быстрых алгоритмов сортировки. Алгоритмы сортировки стремятся взять список чисел и вернуть их от наименьшего к наибольшему. Поскольку очень многие приложения полагаются на быструю сортировку, поиск алгоритма, который может отсортировать список наиболее быстро, представляет большой интерес. Некоторые из самых быстрых алгоритмов используют рекурсивный подход «разделяй и властвуй».
Разделяй и властвуй - это стратегия, в которой исходная проблема рекурсивно разбивается на несколько подзадач. После того, как каждая подзадача имеет единичный размер (аналогично базовому случаю), для каждой из подзадач находятся субрешения, и субрешения снова рекурсивно объединяются, чтобы сформировать полное решение.
Рассмотрим, например, QuickSort, один из самых быстрых алгоритмов сортировки, который при правильной реализации может работать в 2–3 раза быстрее, чем его конкуренты и предшественники.
QuickSort начинается с выбора «точки поворота». В наивных реализациях и для наших целей точка поворота является произвольной, но более специализированные реализации осторожны в выборе точки поворота.
Все элементы, меньшие, чем точка поворота, перемещаются влево от поворота, а все элементы, размер которых превышает размер поворота, перемещаются вправо. Это можно сделать, пройдя по каждому из элементов, переместив их в один список, если их значение меньше, чем у сводной таблицы, и в другой список, если ее значение больше, чем у сводной таблицы. Обратите внимание, что эта операция решает задачу лишь частично.
Процесс разделения списка по его опорной точке называется секционированием, потому что опорная точка делит список на две части или стороны. Каждый раздел вызывает для себя другую итерацию разделения и так далее, пока раздел не достигнет базового случая (1 единица, просто одно число).
После достаточного количества рекурсии исходный список будет достаточно разделен до такой степени, что рекурсия больше не может быть вызвана. На этом этапе состав субрешений состоит просто в том, чтобы сложить их вместе по горизонтали. Результатом композиции является отсортированный список.
Обратите внимание, что QuickSort следует за многими стандартными блоками рекурсии, обсуждавшимися ранее, только на более высоком уровне. Отношение рекуррентности - это разделение компонента, а базовый случай - это раздел размером 1. Начиная с исходного списка, те же процессы (выбор точки поворота, раздела) вызываются рекурсивно, пока результат не будет состоять только из базовых вариантов.
Ключевые моменты
- Рекурсия - это подход к программированию, который вызывает себя внутри функции, позволяя создавать циклы и автоматическое построение дерева с минимальным кодом.
- При построении любой рекурсивной функции необходимо четко понимать два элемента: рекуррентное отношение и базовый случай.
- Мемоизация - это метод предотвращения дублирования операций путем сохранения информации в кеше и последующего их извлечения при необходимости.
- Разделяй и властвуй - это одно из многих более глубоких приложений рекурсии, в котором проблема рекурсивно разбивается на несколько подзадач (базовых случаев), из которых можно легко извлечь и объединить подрешения для формирования полного решения.
Хотите увидеть больше примеров рекурсии на практике? Ознакомьтесь с этой статьей об отслеживании с возвратом, варианте рекурсии, который часто является хорошей стратегией при поиске. Используйте поиск с возвратом для решения таких задач, как судоку, с помощью кода:
Все изображения созданы автором
