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

Question

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

На мой взгляд, рекурсивные алгоритмы естественным образом подходят, когда структура данных также рекурсивна.

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

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

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

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

    }

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