"Необходимые" способы рекурсии на императивных языках

Недавно я видел в нескольких разных местах комментарии по следующим темам: "Я узнал о рекурсии в школе, но никогда не использовал ее или не ощущал ее необходимости с тех пор". (Рекурсия кажется популярным примером "книжного обучения" среди определенной группы программистов.)

Ну, верно, что на императивных языках, таких как Java и Ruby [1], мы обычно используем итерацию и избегаем рекурсии, частично из-за риска, а отчасти потому, что это стиль большинства программистов на этих языках используются.

Теперь я знаю, что, строго говоря, нет "необходимых" использования рекурсии на таких языках: всегда можно каким-то образом заменить рекурсию на итерацию, независимо от того, насколько сложны вещи. Здесь "необходимо", я говорю о следующем:

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

В ответах несколько раз упоминались рекурсивно ходячие деревья: что было именно в вашем конкретном использовании, что сделало рекурсию лучше, чем использование библиотечного итератора, если бы она была доступна?

[1]: Да, я знаю, что это также объектно-ориентированные языки. Однако это не имеет прямого отношения к этому вопросу.

Ответ 1

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

Практически говоря, если вы не используете рекурсию для следующих (даже на императивных языках), вы немного сумасшедшие:

Обход дерева
Графы
Lexing/Синтаксический
Сортировка

Ответ 2

Когда вы идете по любой древовидной структуре, например

разбор грамматики с использованием парсера рекурсивного спуска
прохождение дерева DOM (например, проанализированного HTML или XML)

также каждый метод toString(), который вызывает toString() членов объекта, также может считаться рекурсивным. Все алгоритмы сериализации объектов являются рекурсивными.

Ответ 3

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

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

Ответ 4

Наиболее известным примером является, вероятно, алгоритм быстрой сортировки, разработанный C.A.R. Хор.

Другим примером является перемещение дерева каталогов для поиска файла.

Ответ 5

По-моему, рекурсивные алгоритмы являются естественным приложением, когда структура данных также рекурсивна.

def traverse(node, function):
    function(this)
    for each childnode in children:
        traverse(childnode, function)

Я не понимаю, почему я хотел бы написать это итеративно.

Ответ 6

Это все о данных, которые вы обрабатываете.

Я написал простой парсер для преобразования строки в структуру данных, это, вероятно, единственный пример за 5 лет работы на Java, но я думаю, что это был правильный способ сделать это.

Строка выглядела так:

"{ index = 1, ID = ['A', 'B', 'C'], data = {" +
   "count = 112, flags = FLAG_1 | FLAG_2 }}"

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

public class ReportDictionary
    {
        private static List<Report> _reportList = null;

        public ReportColumnList this[string screenName]
        {
            get
            {
                Report rc = _reportList.Find(delegate(Report obj) { return obj.ReportName == screenName; });

                if (rc == null)
                {
                    this.Load(screenName);
                    return this[screenName]; // Recursive call
                }
                else
                    return rc.ReportColumnList.Copy();
            }
            private set
            {
                this.Add(screenName, value);
            }
        }

    }

Это можно сделать без рекурсии, используя некоторые дополнительные строки кода.