Вопрос по – «Необходимое» использование рекурсии на императивных языках

11

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

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

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

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

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

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

stackoverflow.com, конечно же! ilya n.
Recursion приводит людей к стекоперемещению ... ilya n.
«Что именно в вашем конкретном использовании сделало рекурсию лучше, чем использование итератора, определенного библиотекой» - я бы поспорил на большие деньги, что вероятная реализация базового итератора использует рекурсию, чтобы получить итеративный интерфейс Russell Leggett
Тело сообщения «где рекурсия была намного лучше, чем итерация» предполагает, что вы знаете, что заголовок сомнителен: нетнеобходим использует рекурсию. AakashM
На самом деле заголовок не идеален: я только что обновил вопрос, чтобы показать, что я это понимаю. Я достаточно обдумал это и не смог найти лучшего слова, которое бы правильно отражало дух вопроса. Не стесняйтесь предложить один. Curt J. Sampson

Ваш Ответ

9   ответов
9

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

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

Обход дере Графы Lexing / СинтаксическийСортировк
Смотрите пост и комментируйте его для обсуждения необходимого слова. Curt J. Sampson
Ответ отвечает на вопрос, заданный в то время. Kevin Montrose♦
Если вы хотите попытаться превратить это в обсуждение вопроса, который я никогда не собирался задавать, продолжайте. В противном случае отредактируйте свой ответ соответствующим образом. Curt J. Sampson
Ответ также соответствует текущему вопросу. Kevin Montrose♦
Только если вы намеренно истолковываете слово «необходимо» иначе, чем я хотел. Пожалуйста, интерпретируйте «необходимо» в этом контексте как сокращение для «необходимо, если вы хотите, чтобы вас не считали немного сумасшедшим с практической точки зрения». В этом свете ваш ответ противоречи Curt J. Sampson
6

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

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

Совершенные примеры. + 1 peSHIr
toString () не является рекурсивным, а сериализация не всегда рекурсивной. Исключением может быть список списков или карта карт, но обычно это не так. G B
Они отличаются методами toString () и serialize (), если только сама структура не является рекурсивной. Рекурсия включает в себя вызов одной и той же функции, а не функции с тем же именем. Robert Fraser
One может рассматривать каждую реализацию toString () как принадлежащую «одной и той же» функции, поскольку все они переопределяют Object.toString (). В неOO-языке toString () может быть реализован как toString (Object) с гигантской диспетчеризацией на основе типов, что, несомненно, будет считаться рекурсивным. mfx
Хороший общий смысл, но я лично не буду делать рекурсию по дереву DOM. Я не знаю, может быть, я слишком консервативен в отношении «никогда не доверяй данным клиента». ilya n.
4

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

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

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

5

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

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

1

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

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

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

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

5

разработанный С.А.Р. Хор.

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

+ 1 для обхода каталога. Очень распространенная задача, которая является настоящей болью, пока вы не попробуете рекурсию. erikkallen
1

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

1

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

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

0

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

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);
            }
        }

    }

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

Похожие вопросы