Что такое рекурсия в программировании и как ее использовать?
Рекурсия — важная часть функционального программирования, которая может помочь решить сложные проблемы с помощью элегантных решений. Тем не менее, важно понимать все за и против, чтобы сделать это правильно.
Что такое рекурсия?
Короткий ответ заключается в том, что рекурсия в основном возникает всякий раз, когда функция вызывает сама себя, обычно с другим вводом, передаваемым дочерней функции. Он вызывает себя снова и снова, пока не будет достигнуто условие выхода, а затем передает результаты обратно в стек вызовов, потенциально изменяя их также по пути вверх.
Длинный ответ заключается в том, что рекурсия может помочь решить сложные проблемы, разбивая их на более мелкие подмножества основной проблемы. Часто у вас будут структуры данных, содержащие вложенные данные. Разбив это на меньшие объемы данных, это облегчит обработку.
Например, предположим, что у каждого листа в дереве есть связанное с ним значение, и мы хотим найти сумму всех значений. Мы могли бы сделать это с помощью функции, подобной следующей, которая обходит дерево лист за листом, проверяя всех дочерних элементов и вычисляя общее количество.
int CountAllLeaves(Leaf currentLeaf)
{
// Start with the current value
int Total = currentLeaf.value;
// Add any children to the value, if any
foreach(Leaf childLeaf in currentLeaf.children)
{
Total = Total + CountAllLeaves(childLeaf);
}
return Total;
}Это работает, потому что CountAllLeaves не волнует, с каким листом вы его вызываете. Он неоднократно вызывает сам себя, пока не дойдет до последнего листа дерева, у которого нет потомков. Из-за этого он просто возвращает свое собственное значение. Это значение передается родительскому листу, который добавляет дочернее значение к своему собственному, а затем повторяется для всех братьев и сестер, которые есть у дочернего листа. В конце концов, окончательным результатом функции будет общая сумма всех листьев в дереве.
В какой-то момент вы должны добраться до остановки, которая представляет собой часть проблемы, ответ на которую вы знаете, не делая больше рекурсивных вызовов. В противном случае функция будет зацикливаться бесконечно, что приведет к сбою программы. В этом случае случай остановки — это когда функция достигает листа, у которого нет дочерних элементов.
Это не обязательно должны быть вложенные структуры данных, такие как деревья. Вы можете написать рекурсивные функции для любого типа проблемы. Например, вычисление факториала числа включает его умножение на каждое меньшее число. Вы можете сделать это очень легко с помощью рекурсии:
int Factorial(int n)
{
if (n <= 1)
return 1;
return n * Factorial(n-1);
}В этом примере случай остановки — это когда n достигает 1, когда он, наконец, возвращает значение, и стек вызовов может быть свернут.
Давайте посмотрим на реальный пример. В этом фрагменте кода есть класс Container , который содержит несколько присоединенных к нему элементов пользовательского интерфейса, а также несколько дочерних контейнеров со своими собственными элементами. Он должен быть преобразован в плоский список элементов, которые можно отобразить на экране.
По сути, это другая древовидная структура данных, поэтому подход аналогичен. За исключением этого случая, переменная total представляет собой список, который получает списки элементов каждого добавленного к нему контейнера.
Магия выполнения этого с помощью рекурсии заключается в том, что она сохраняет Z-порядок элементов. Элементы, нарисованные после других элементов, располагаются сверху, поэтому самый младший дочерний контейнер всегда будет отображаться сверху. В этом сценарии я также счел полезным отображать элементы наложения, которые добавляются после завершения рендеринга других элементов и дочерних элементов.
Опасности рекурсии
Итак, когда вы должны использовать рекурсию в своем коде? Ответ заключается в том, что вам, вероятно, следует избегать этого в большинстве ситуаций, особенно когда итеративное решение с использованием простого цикла выполняет свою работу.
Каждый раз, когда вы вызываете функцию, ваша программа выделяет ресурсы для этой функции. Все локальные переменные и информация попадают в стек, который представляет собой структуру данных «последним пришел — первым вышел» (LIFO). Это означает, что последний вызов функции всегда удаляется первым, как ведро, из которого вы всегда удаляете верхний элемент.
Проблема с рекурсией заключается в том, что она может использовать вызов вложенной функции для каждого обрабатываемого элемента. Это приводит к гораздо большим накладным расходам, поскольку для каждого вызова функции требуется собственный набор локальных переменных и параметров. Это потребует дополнительного времени обработки по сравнению с подходом, основанным на циклах.
У циклов нет этой проблемы. После каждой итерации цикла в стеке будет очищаться верхний элемент. Он мог обрабатывать миллиард элементов, используя один и тот же стек.
Если вы используете слишком много ресурсов с рекурсивными вызовами функций, это может привести к переполнению стека, когда программа может завершить работу из-за слишком большого количества вложенных вызовов. Это может произойти с особенно большими наборами данных или с плохими алгоритмами, такими как двоичная или экспоненциальная рекурсия, которые вызывают себя несколько раз за вызов функции.
Используйте рекурсию экономно
Рекурсия полезна для решения определенных задач, но в принципе не существует рекурсивных решений проблем, которые нельзя было бы решить с помощью циклов (за исключением вложенной рекурсии, такой как функция Аккермана). Даже сложные древовидные структуры данных можно обходить с помощью циклов и стеков. Если вам нужно обрабатывать большие объемы данных или сильно заботиться о производительности, возможно, вам лучше использовать итеративное решение.
Другая проблема с рекурсией заключается в том, что она может привести к коду, который трудно понять другим людям, поскольку обычно требуется немного почесать голову, прежде чем кто-то его поймет. Хотя это часто кажется более «элегантным» решением, ваша работа как программиста состоит не в том, чтобы хвастаться, а в том, чтобы писать функциональный, читаемый код.
В любом случае, вы захотите подумать о том, будет ли лучше решить проблему с помощью цикла. Рекурсия должна быть вашим последним средством для решения проблем, которые без нее были бы намного сложнее. Фактически, из всех моих 40 000 строк исходного кода у меня был только один пример рекурсии для этой статьи.
И, после второго взгляда на него, я действительно заметил проблему. Хотя он работал нормально, он был написан ленивым, очевидным способом, и поэтому использует гораздо больше памяти, чем ему нужно. На самом деле это не проблема с небольшими структурами данных, которые он обрабатывает, но он создавал new List для каждого вызова функции и добавлял результаты дочерних элементов под ним. . Это означало, что если ему дали контейнер с глубоко вложенными дочерними элементами, он будет хранить одни и те же данные снова и снова без всякой причины.
Решением в этом случае было передать рекурсивной функции ссылку на внешний список и добавить в него все элементы напрямую. Это также включало изменение функции Render() на функцию, которая обрабатывала настройку верхнего уровня для функции рекурсивной сборки.
Это дает точно такое же решение добавления каждого элемента в правильном порядке, но устраняет проблему экспоненциального увеличения использования памяти с каждым вызовом.
Тем не менее, я доволен этой функцией, поскольку она довольно лаконична и легко выполняет свою работу. Если бы я преобразовал это в решение с использованием цикла, это было бы намного сложнее и делало бы то же самое. Вам нужно будет взвесить все за и против использования рекурсивного решения и использовать их только там, где вы не ожидаете серьезного использования ресурсов. В данном случае я не ожидаю вызова этой функции с вложенными контейнерами, содержащими сотни элементов, поэтому здесь можно использовать рекурсию.
Для получения дополнительной информации по этой теме см. наше руководство по рекурсии.