Рекурсивные и нерекурсивные процедуры для деревьев


так как мы знаем, что деревья являются рекурсивными структурами данных, мы используем рекурсию в написании процедур дерева, таких как метод удаления BST и т. д.
Преимущество рекурсии состоит в том, что наши процедуры становятся очень маленькими (например, код обхода по порядку имеет всего 4 или 5 строк), а не неповторяющейся процедурой, которая была бы длительной, но не такой сложной, как рекурсивная процедура для понимания перспективы. Вот почему я ненавижу рекурсию, и я предпочитаю писать нерекурсивную процедуру, и я сделал это в двоичных деревьях поиска и avl-деревьях.
Теперь уточните, что предпочтение нерекурсивных процедур над рекурсивными - это плохо или хорошо."

Источник

4 ответа

Решение

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

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

"Каноническая" рекурсивная функция (факториал) показана ниже как в рекурсивной, так и в итерационной формах, и, на мой взгляд, рекурсивная форма более четко отражает математическое определение f(1) = 1, f(n) = n*f(n-1) for n>1,

Iterative:                    Recursive:
def fact(n):                  def fact(n):
    r = n                         if n == 1:
    while n > 1:                      return 1
        r = r * n                 return n * fact(n-1)
        n = n - 1
    return r

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

  1. Большинство стеков могут быть настроены в случае необходимости.
  2. Рекурсия (особенно хвостовая рекурсия, где рекурсивный вызов - это последнее, что происходит в функции) обычно может быть оптимизирована для итеративного решения интеллектуальным компилятором.
  3. Большинство алгоритмов, которые я использую в рекурсивных ситуациях (таких как сбалансированные деревья и т. Д., Как вы упоминаете), имеют тенденцию быть O(logN) и использование стека не растет так быстро с увеличением объема данных. Например, вы можете обработать дерево с 16 путями, хранящее два миллиарда записей только с семью уровнями стека (167 = ~ 2,6 миллиарда).
Источник

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

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

Источник

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

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

Источник

Рекурсия - это инструмент. Иногда использование "инструмента рекурсии" облегчает чтение кода, хотя не обязательно облегчает его понимание.

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

Как правило, рекурсия хорошо подходит, когда вы можете посмотреть на проблему и сказать: "Ага, если бы я знал ответ для более простого варианта этой проблемы, я мог бы использовать это решение для генерации нужного мне ответа" и "Простейшая возможная проблема". является P, и его решение является S". Затем код для решения проблемы в целом сводится к просмотру внутренних данных, их упрощению, рекурсивному генерированию (более простого) ответа и переходу от более простого ответа к ответу в целом.

Если мы рассмотрим проблему подсчета уровней дерева, ответ будет таков: высота дерева на 1 больше, чем высота самого высокого / самого глубокого из детей, а высота листа равна 1. Что-то вроде следующий код Эта проблема может быть решена итеративно, но, по сути, вы бы заново реализовали стек вызовов в своих собственных структурах данных.

def tree_height (дерево):
  if tree.is_leaf():
    возврат 1

  childmax = 0;
  для ребенка в tree.children():
    childmax=max(childmax, tree_height(child))

  возврат childmax+1

Также стоит учесть, что Tail Call Optimization может сделать некоторые рекурсивные функции работающими в пространстве постоянного стека.

Источник
Другие вопросы по тегам