Недавно я закончила стипендию программной инженерии для женщин в Академии Хакбрайт. За 10 недель учебный курс научит вас, как создать работающее веб-приложение (Ознакомьтесь с приложениями, созданными моими замечательными коллегами!), А также научит вас фундаментальным темам в области CS, таким как структуры данных, алгоритмы и рекурсия. Это был большой объем информации, который нужно было охватить за короткий промежуток времени, и темой, с которой я и другие, казалось, больше всего боролись, была рекурсия.
Ничто не вызывает большего страха в недавнем выпускнике учебного лагеря, чем просьба закодировать рекурсивную проблему на доске.
Я хотел написать это сообщение в блоге, чтобы поделиться своими идеями, которые я получил во время изучения рекурсии, и, надеюсь, демистифицировать ее, казалось бы, волшебные свойства. Этот блог будет наиболее полезен для учащихся, которые самостоятельно решали несколько рекурсивных задач, но пока не чувствуют себя в этом комфортно.
Во-первых, что такое рекурсия? Это функция, которая вызывает сама себя. Вот и все. Не попадитесь в ловушку мысли, что рекурсия обязательно исключает циклы for / while. Хотя часто это так, существует множество рекурсивных функций, которые по-прежнему реализуют циклы (подробнее об этом позже). Фактически, поскольку рекурсия имеет такое широкое определение, часто существует множество различных рекурсивных стратегий для решения одной и той же проблемы.
Поскольку рекурсивная функция вызывает сама себя, ей нужен базовый случай. В противном случае функция вызывала бы себя навсегда. В конце концов у вас закончится память в вашем стеке (та часть памяти вашего компьютера, которая выделена для вызовов функций), и это называется переполнением стека. Многие рекурсивные функции начинаются с оператора if, который проверяет базовый случай. Однако не каждая рекурсивная функция имеет такой очевидный или явный базовый случай.
Моя диссертация:
Большинство из нас не может уследить за полным стеком вызовов в своей голове. Таким образом, рекурсия, как и большинство инженерных задач, касается сопоставления с образцом. Это означает, что при наличии различных рекурсивных шаблонов и достаточной практики любой может сделать это хорошо. Часто инструкторы и интервьюеры побуждают вас «подумать о базовом и рекурсивном случаях», как будто интуиция, лежащая в основе этих вещей, должна быть очевидна. Ну это не так! То есть до у вас будет достаточно практики с различными рекурсивными шаблонами. Теперь я продемонстрирую несколько распространенных рекурсивных шаблонов на примерах на Python.
Первые три шаблона решают одну и ту же проблему: подсчет количества элементов в списке. Самый простой способ решить эту проблему - использовать встроенный в python метод len () для списков, но предположим, что в нашем распоряжении этого нет. Мы могли бы решить эту проблему итеративно:
Теперь давайте подумаем, как решить эту проблему рекурсивно. Первое, что я хочу подчеркнуть, это то, что всякий раз, когда мы работаем с итерациями, такими как списки или строки в рекурсивной функции, мы, вероятно, захотим использовать нарезку для достижения прогресса. Подумайте об этом, как мы можем разбить проблему, включающую длинную итерацию, на более простую задачу? Разбейте его на последовательно меньшие итерации, пока мы не дойдем до тривиального случая - например, пустой список или пустая строка.
Что еще более важно, у этого нет единственного решения. Теперь я выделю три различных рекурсивных шаблона для решения этой проблемы.
Шаблон 1. Результат накапливается в операторе возврата
Первое решение работает путем добавления счетчика, вместе с разрезанным списком, в оператор возврата. По сути, он добавляет 1 каждый раз, когда мы выполняем рекурсию, и мы выполняем рекурсию n раз.
Если бы наш список был [1, 2, 3], наши вызовы функций выглядели бы так:
1 + [2, 3] 1 + 1 + [3] 1 + 1 + 1 + [] 1 + 1 + 1 + 0
Единственный нюанс здесь - это базовый случай. Наш базовый случай - когда мы достигаем пустого списка. Нам нужно что-то вернуть из этого вызова, иначе мы никогда не перестанем повторяться. Но что? Оно должно быть целым числом, потому что, если мы вернем что-то еще, например None или пустой список, мы вызовем ошибку, когда попытаемся добавить его к другим вызовам наших функций. Следовательно, мы возвращаем ноль.
Этот рекурсивный шаблон хорош для решения проблем, которые в противном случае мы могли бы решить, повторяя цикл for и добавляя или добавляя что-то на каждом шаге. Точно так же, как вы могли бы подумать о цикле по итерируемому объекту, подумайте о возврате [результата текущего элемента] + [функции, вызываемой для остальной итерации]. Некоторые другие проблемы, которые легко поддаются этому же шаблону, - это суммирование чисел в списке и перестановка строки.
Шаблон 2. Возвращаемое значение - аргумент функции
В решении 2 мы передаем то, что хотим вернуть, - переменную count - в качестве аргумента нашей функции. Этот шаблон является примером так называемой хвостовой рекурсии, и у этого аргумента есть специальное имя, аккумулятор. Что отличает хвостовую рекурсию от традиционной рекурсии , заключается в том, что последний вызов функции содержит все, что необходимо для выполнения последнего оператора возврата. В этом примере мы возвращаем значение переменной count при последнем вызове и игнорируем значения из предыдущих вызовов функций. Накопительные переменные являются обычным явлением в хвостовых рекурсивных решениях, но они не являются строго обязательными.
В некоторых языках, таких как Scheme и JavaScript, хвостовые рекурсивные решения имеют преимущество в оптимизации памяти по сравнению с традиционными рекурсивными решениями. Подумайте об этом, мы можем забыть обо всех других функциях, хранящихся в стеке вызовов, и сохранить в памяти только самый последний вызов. Однако Python - это язык, который не допускает такой оптимизации, потому что его создатель, Гвидо Ван Россум, предпочел, чтобы у него были надлежащие трассировки функций для целей отладки.
В этом примере наши вызовы функции для [1, 2, 3] выглядят так:
count_recr2([2,3], count=1) count_recr2([3], count=2) count_recr2([], count=3)
Паттерн 3: Накопите счетчик в переменной, иначе WTF ???
Этот конкретный паттерн по-настоящему изгибает сознание. Разве переменная count не сбрасывается в 1 каждый раз, когда вы вызываете функцию? Да, да, это так. Но в этом и заключается магия рекурсии. Каждый рекурсивный вызов - это отдельный вызов функции, и поэтому он поддерживает свой собственный набор локальных переменных. Это означает, что для списка [1, 2, 3] в стеке вызовов есть три разных кадра, каждый с переменной count, установленной на значение 1. Когда мы достигаем нашего базового случая, мы возвращаем ноль. Затем наша функция наверху стека возвращает 1 предыдущей функции и так далее, пока все счетчики не будут накоплены в нашей переменной count из нашего первого вызова функции. Я все еще скептически отношусь к этому, но он помогает визуализировать его в визуализаторе Python.
Это решение по сути то же самое, что и решение 1, за исключением того, что счетчик сохраняется в переменной перед его возвратом. Однако я хотел использовать этот пример, чтобы проиллюстрировать, как область видимости переменной работает в рекурсивной функции. Это также появляется в следующем примере. . .
Паттерн 4: когда рекурсия встречается с итерацией
Еще один непонятный для меня паттерн - это рекурсивные функции, включающие итерационные циклы. Эта закономерность возникает, когда у вас есть своего рода вложение. В приведенном ниже примере мы хотим подсчитать количество узлов в дереве. Потомки узла хранятся в списке, поэтому нам нужно перебрать каждого из потомков. Затем для каждого потомка нам нужно пройти и посчитать их соответствующих потомков.
Обратите внимание: этот код очень похож на Решение 3, приведенное выше, когда мы подсчитывали элементы в списке.
При использовании цикла внутри рекурсивной функции важно следить за оператором return. Если мы вернемся внутрь цикла for, он не завершит цикл. Вот почему паттерны 1 и 2 не подходят для этого примера. Просто помните, не возвращайтесь внутрь цикла for, если вы не достигли окончательного варианта выигрыш или проигрыш. Другие проблемы кодирования, использующие этот шаблон, - это поиск в глубину и генерация перестановок.
Паттерн 5: внутренние рекурсивные функции
Когда я впервые увидел этот шаблон, он показался мне обманом, но это вполне верное решение. Идея состоит в том, чтобы определить внутреннюю функцию, которая является рекурсивной внутри нерекурсивной функции. По соглашению эта внутренняя функция называется так же, как и внешняя, но с подчеркиванием в начале, указывающим, что это вспомогательная функция, которую следует использовать только локально.
Этот шаблон полезен, когда вам нужно пройти по структуре данных и затем сделать что-то еще, что зависит от объекта в первоначальном вызове. Обход легко рекурсивно закодировать, а последние шаги можно определить во внешней нерекурсивной функции.
В качестве примера я воспользуюсь перестановкой связанного списка на место. Мы просматриваем наш связанный список и меняем направление каждой стрелки при каждом рекурсивном вызове. Однако, когда мы дошли до конца нашего списка, нам нужно обновить заголовок исходного списка. Почему мы не можем сделать это в нашей рекурсивной функции? Из-за объектной ориентации. Если бы мы решили эту проблему с помощью одной рекурсивной функции, мы бы каждый раз передавали новый экземпляр связанного списка. Когда мы дойдем до конца нашего связанного списка, не будет возможности вернуться к исходному экземпляру и изменить его заголовок.
Заключение:
Ознакомление с этими и другими рекурсивными шаблонами упростит решение проблем рекурсии. Для любой конкретной проблемы рекурсии подумайте, на какой шаблон она больше всего похожа. Имейте в виду, что часто может работать несколько шаблонов. Я обнаружил, что лучший способ попрактиковаться в рекурсии - это решить проблему итеративно, затем решить ее рекурсивно, а затем снова попытаться решить ее с помощью другого рекурсивного шаблона. На самом деле, больше всего я узнал из долгих размышлений о том, почему определенные шаблоны не подходят для решения определенных проблем. Таким образом, вы можете проверить границы каждого рисунка. Удачи и удачи!
