Что такое рекурсия в программировании и как ее использовать? — CloudSavvy ИТ

Shutterstock / Ольга ДончукРекурсия — важная часть функционального программирования, которая может помочь решить сложные проблемы с помощью элегантных решений. Однако важно понимать плюсы и минусы, чтобы сделать это правильно.

Что такое рекурсия?

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

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

Например, предположим, что каждый лист в дереве имеет значение, связанное с ним, и мы хотели найти сумму всех значений. Мы могли бы сделать это с помощью функции, подобной следующей, которая просматривает дерево лист за листом, проверяя всех дочерних элементов и вычисляя общую сумму.
int CountAllLeaves (Leaf currentLeaf) {// Начать с текущего значения int Total = currentLeaf.value; // Добавляем дочерние элементы к значению, если есть foreach (Leaf childLeaf в currentLeaf.children) {Total = Total + CountAllLeaves (childLeaf); } return Total; }
Это работает, потому что CountAllLeaves не заботится о том, каким Leaf вы его вызываете. Он неоднократно вызывает себя, пока не достигнет последнего листа дерева, у которого нет дочерних элементов. Из-за этого он просто возвращает собственное значение. Это значение передается родительскому листу, который добавляет дочернее значение к своему собственному, а затем повторяется для всех братьев и сестер, которые есть у дочернего листа. В конце концов, конечным результатом функции будет общая сумма всех листьев в дереве.

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

Это не обязательно должно быть о вложенных структурах данных, таких как деревья. Вы можете написать рекурсивные функции для решения любого типа проблемы. Например, вычисление факториала числа включает его умножение на каждое меньшее число. Вы можете сделать это очень легко с помощью рекурсии:
int Factorial (int n) {если (n <= 1) вернуть 1; return n * Факториал (n-1); }
В этом примере случай остановки — когда n достигает 1, когда он, наконец, возвращает значение, и стек вызовов может быть свернут.

Давайте посмотрим на реальный пример. В этом фрагменте кода есть класс Container, который содержит несколько прикрепленных к нему элементов пользовательского интерфейса, а также несколько дочерних контейнеров со своими собственными элементами. Он должен быть преобразован в плоский список элементов, которые могут отображаться на экране.

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

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

Опасности рекурсии

Итак, когда вам следует использовать рекурсию в своем коде? Ответ заключается в том, что вам, вероятно, следует избегать этого в большинстве ситуаций, особенно когда итеративное решение с использованием простого цикла выполнит свою работу.

Каждый раз, когда вы вызываете функцию, ваша программа выделяет ей ресурсы. Все локальные переменные и информация попадают в стек, который представляет собой структуру данных «последний пришел — первым ушел» (LIFO). Это означает, что последний вызов функции всегда удаляется первым, как корзина, из которой вы всегда удаляете верхний элемент.

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

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

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

Экономно используйте рекурсию

Рекурсия — это хорошо для определенных проблем, но в основном нет рекурсивных решений проблем, которые также не могут быть решены с помощью циклов (за исключением вложенной рекурсии, такой как Функция Акермана). Даже сложные древовидные структуры данных можно обходить петлями и стеками. Если вам нужно обрабатывать большие объемы данных или сильно заботиться о производительности, вам может быть лучше использовать итеративное решение.

Другая проблема с рекурсией заключается в том, что она может привести к коду, который трудно понять другим людям, поскольку обычно требуется немного почесать голову, прежде чем кто-то его получит. Хотя это часто кажется более «элегантным» решением, ваша задача как программиста — не выставлять напоказ, а вместо этого писать функциональный, читаемый код.

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

И, взглянув на него второй раз, я действительно заметил проблему. Хотя он работал нормально, он был написан ленивым, очевидным способом и поэтому использует гораздо больше памяти, чем нужно. На самом деле это не проблема с небольшими структурами данных, которые он обрабатывает, но он создавал новый List () для каждого вызова функции и добавлял результаты дочерних элементов под ним. Это означало, что если бы ему был предоставлен контейнер с глубоко вложенными дочерними элементами, он бы без всякой причины сохранял одни и те же данные снова и снова.

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

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

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

Дополнительные сведения по этой теме см. В нашем руководстве по рекурсии.

Похожие записи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *