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

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

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

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

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

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

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

Вероятно, наиболее известным примером является алгоритм быстрой сортировки, разработанный CAR Hoare.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    }

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

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