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

Question

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

Answer 1

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

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

«Каноническая» рекурсивная функция (факториал) показана ниже как в рекурсивной, так и итеративной формах, и, на мой взгляд, рекурсивная форма более четко отражает математическое определение 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 путями, хранящее два миллиарда записей только с семью уровнями стека (16 ⁷ = ~ 2,6 миллиарда).

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

def tree_height (tree):
  if tree.is_leaf():
    return 1

  childmax = 0;
  for child in tree.children():
    childmax=max(childmax, tree_height(child))

  return childmax+1

Стоит также учитывать, что оптимизация вызовов Tail может заставить некоторые рекурсивные функции выполняться впостоянное пространство стека.