О бедной рекурсии замолвите слово, или всё, что вы не знали и не хотите о ней знать

  • Tutorial
Рекурсия: см. рекурсия.

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

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

— Как она сложена?
— Превосходно! Только рука немного торчит из чемодана.

Именно пытаясь разместить стройную теорию алгоритма в жесткий рюкзак реальных ресурсов и приходится постоянно кроить по живому, перепаковывать, и вместо красивых и стройных определений Фибоначчи:

  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    if n>1: return fib(n-1) + fib(n-2)
    return n

приходится городить всевозможные грязные хаки, начиная от:

  @memoized
  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    if n>1: return fib(n-1) + fib(n-2)
    return n

И заканчивая вообще:

  def fib(n):
    if n<0: raise Exception("fib(n) defined for n>=0")
    n0 = 0
    n1 = 1
    for k in range(n):
      n0, n1 = n1, n0+n1
    return n0


Так что же такое рекурсия?


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

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

Теперь давайте рассмотрим классический пример: обход дерева в глубину. Впрочем нет, давайте рассмотрим другой пример: нам надо распечатать дерево выражений в форме обратной польской записи. То есть для дерева 1 мы хотим напечатать «2 2 +» а для дерева 2 «2 2 + 2 2 + *».

tex
\begin{tikzpicture}
	\node (is-root) {+}
		child { node {2} }
		child { node {2} };
	\path (is-root) +(0,+0.5\tikzleveldistance)
		node {\textit{Tree 1}};
\end{tikzpicture}
\begin{tikzpicture}
	\node (is-root) {*}
		child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} }
		child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} };
	\path (is-root) +(0,+0.5\tikzleveldistance)
		node {\textit{Tree 2}};
\end{tikzpicture}


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

class TreeNode(object):
  def __init__(self, value=None, children=[]):
    self.value = value
    self.children = children
def printTree(node):
  for child in node.children:
    printTree(child)
  print node.value,
def main():
  tree1 = TreeNode("+", [ TreeNode(2), TreeNode(2) ])
  tree2 = TreeNode("*", [ TreeNode("+", [ TreeNode(2), TreeNode(2) ]), TreeNode("+", [ TreeNode(2), TreeNode(2) ]) ])
  print "Tree1:",
  printTree(tree1)
  print

  print "Tree2:",
  printTree(tree2)
  print
if __name__ == "__main__":
  main()


Казалось бы, всё отлично! Код прекрасно работает до тех пор, пока дерево соответствует требованиям: любой узел имеет массив детей (возможно пустой) и какое-либо значение. Кто скажет какое еще требование к этому дереву?



Не буду томить. Требование: не сильно большая глубина дерева. Как так? А вот как:

def buildTree(depth):
  root = TreeNode("1")
  node = root
  for k in range(depth):
    node = TreeNode("--", [ node ])
  return node

def depthTest(depth):
  tree = buildTree(depth)
  print "Tree of depth", depth, ":",
  printTree(tree)

def main():
   for d in range(10000):
     depthTest(d)

Запускаем, и ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Лезем в документацию, и обнаруживаем функцию sys.getrecursionlimit. А теперь давайте отойдём от мира интерпретируемых языков, и перейдём в мир языков, которые запускаются прямо на процессоре. Например, на C++.

Мысленно перепишем 1-в-1 этот код на С++ (оставлю эту задачу читателю в качестве разминки), и попробуем найти предел, когда приложение упрется в ограничение…

для ленивых
#include <string>
#include <vector>
#include <iostream>

using namespace std;

class TreeNode {
public:
  string value_;
  vector<TreeNode*> children_;

  TreeNode(const string& value, const vector<TreeNode*>& children):
      value_(value), children_(children) {}

  virtual ~TreeNode() {}
};

void printTree(const TreeNode* node) {
  for(auto i : node->children_)
    printTree(i);
  cout << node->value_ << " ";
}

TreeNode* buildTree(const int depth) {
  auto root = new TreeNode("1", {});
  auto node = root;
  for(int i = 0; i<depth; i++) {
    vector<TreeNode*> children;
    children.push_back(node);
    node = new TreeNode("--", children);
  }
  return node;
}

void depthTest(const int depth) {
  auto tree = buildTree(depth);
  cout << "Tree of depth " << depth << ": ";
  printTree(tree);
  cout << endl;
}

int main() {
  for(int d=60000;; d+=16384) {
      depthTest(d);
  }
}

Запускаем… «Bus error (core dumped)». Судя по gdb, в момент падения стек глубиной 104790 фреймов. А что произойдёт, если мы захотим печатать не просто подряд через пробелы, а выводить еще "{" и "}" вокруг выражений? Ну то есть для дерева 1 чтобы результатом было {2 2 +} а для дерева 2 — {{2 2 +}{2 2 +}*}? Перепишем…

def printTree(node):
  opened = False
  for child in node.children:
    if not opened:
      print "{",
      opened = True
    printTree(child)
  print node.value,
  if opened:
    print "}",


Ничего не изменилось, по прежнему падает при попытке распечатать дерево глубиной 997. А теперь то же самое, но на плюсах… Опа. Глубина стека при падении — 87327. Стоп. Мы всего-то добавили одну локальную переменную, никак не влияющую на алгоритм и суть происходящего, а предельный размер дерева сократился на 17%! А теперь самое весёлое — всё это сильно зависит от опций компилятора, от того, на какой платформе выполняется, в какой ОС и с какими настройками.

Но не это самое смешное. Давайте представим, что эту функцию использует другая функция. Всё хорошо, если она одна такая — мы можем подсчитать, на сколько же фактических шагов меньше максимальная глубина. А если эта функция используется из другой рекурсивной? Тогда возможности этой функции будут зависеть от глубины другой функции.

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

Так в чем же проблема?


Использование рекурсивного алгоритма подразумевает использование практически не контролируемого ресурса: стека вызовов.

Во-1х, мы не можем точно знать сколько уже его использовано. Во-2х, мы не можем точно знать, сколько его еще осталось. В-3их мы не можем гарантировать доступность определённого размера этого ресурса к каждому вызову. В 4-ых, мы не можем фиксировать расход данного ресурса. Таким образом, мы попадаем в зависимость от ресурса, контролировать и распределять который чертовски сложно. В результате, мы не можем гарантировать каких либо характеристик данной функции/сервиса. Хорошо, если наш сервис работает в managed контексте: java, python, .net итп. Плохо, если сервис работает в неконтролируемой среде: javascript (с которым вообще всё плохо). Еще хуже, если сервис работает на C++, и глубина рекурсии зависит от данных, переданных пользователем.

Что же делать?


Если мы работаем не на микроконтроллере, о объёме стека можно не задумываться: для обычной цепочки вызовов его должно хватать. При условии, разумеется, что мы заботимся гигиене локальных переменных: большие объекты и массивы выделяются используя память (new/malloc). Однако использование рекурсии подразумевает, что вместо ограниченного количества вызовов, у нас их будет просто счетное.

Итак, чтобы избавиться от проблем, созданных рекурсией, можно сделать следующее (от простого к сложному):
— Жестко ограничить максимальный размер/формат/числа во входящих данных. Привет, zip бомбам и иже с ними — порой даже маленький входящий пакет может устроить большой переполох.
— Жестко ограничить максимальную глубину вызовов некоторым числом. Важно помнить, что это число должно быть ОЧЕНЬ небольшим. То есть порядка сотен. И обязательно добавить тесты, которые проверяют, что программа с этим максимальным числом не ломается. Причем с максимальным числом на всех возможных ветках исполнения (привет выделению локальных переменных по требованию). И не забывать проверять этот тест на разных опциях компилияции и после каждого билда.
— Жестко ограничить объём используемый стека. Используя сложные обходные маневры и знания о практической реализации исполнения в железе можно получить размер стека, который использован сейчас (типа взятия адреса локальной volatile переменной). В некоторых случаях (например, через libunwind в linux'е) можно получить так же доступный объём стека текущему потоку, и взять между ними разницу. При использовании подобного метода важно иметь тесты, проверяющие, что отсечение работает гарантированно и при всех вариантах входных данных — например, может получиться весело, если проверка идёт в одном методе, который рекурсивен через 3-4 других. И оно может упасть в промежуточном… Но только в режиме релиза, после inline'а некоторых функций, например. Впрочем, тут еще важны тесты на максимальную допустимую сложность, чтобы невзначай не отсечь часть корректных входных запросов, которыми клиенты реально пользуются.
— Лучший способ: избавиться от рекурсии.

И не лги, что ты волен и свят — Ты пленен и неволен.
Я раскрыл пред тобой небосвод!
Времена изменяют свой ход — Посмотри на ладони…

Беспредельная сладость свободы
Отринуть свободу
Сергей Калугин

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

Каноническая нерекурсивная реализацию обхода дерева в глубину:
def printTree(node):
  stack = [ (node, False, False) ]
  while len(stack)>0:
    i = len(stack)-1
    node, visited, opened = stack[i]
    if not visited:
      for child in reversed(node.children):
        if not opened:
          print "{",
          opened = True
        stack.append( (child, False, False) )
      visited = True
      stack[i] = (node, visited, opened)
    else:
      print node.value,
      if opened:
        print "}",
      del stack[i]

Как легко видеть, алгоритм не изменился, но вместо использования стека вызовов используется массив stack, размещенный в памяти, и хранящий как контекст обработки (в нашем случае — флаг opened) так и контекст обработки (в нашем случае — до или после обработки детей). В случаях, когда нужно что-то делать между каждым из рекурсивных вызовов, либо добавляются фазы обработки. Обратите внимание: это уже оптимизированный алгоритм, складывающий всех детей в стек сразу, и именно поэтому складывающий в обратном порядке. Это гарантирует сохранение того же порядка, что и у исходного нерекурсивного алгоритма.

Вот этот же код, только написанный «в лоб», сохраняя контекст (заодно, выводящий запятые между элементами):

def printTree(node):
  stack = [ (node, 0) ]
  while len(stack)>0:
    i = len(stack)-1
    node, phase = stack[i]
    if phase < len(node.children):
      child = node.children[phase]
      if phase == 0:
        print "{",
      if phase > 0:
        print ",",
      stack.append( (child, 0) )
      stack[i] = (node, phase+1)
    else:
      print node.value,
      if phase>0:
        print "}",
      del stack[i]

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

Злоключение


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

А как не используете рекурсию вы?
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 63
  • +2
    Отличный анализ, отличный вывод. Спасибо!

    Понимание того, что стек вызовов — неконтролируемый (ну или плохо контролируемый) ресурс, к сожалению, отсутствует в головах у очень многих программистов. Те немногочисленные интервью, в которых мне довелось участвовать с обоих сторон, отлично это показали.
    • +1
      Просто начиная с момента «щелчка» в мозгах многих, когда достигается внезапное просветление в понимании что есть рекурсия, они помечают это знание как постигнутое… А на самом деле, это лишь пол дела.
      • 0
        Да ладно! Размер стека даже в С++ может быть не ограниченным (точнее ограниченным не более чем размер кучи). :-)
        • +1
          Вот только отдаст ли система твоему модулю неограниченный стек?
          И, самое главное, получишь ли ты null при попытке рекурсии, аналогрично malloc/realloc?
          • +1
            Ну, положим в случае юниксов я и для malloc скорее всего null не получу.

            PS. А операционной системе про мой «стек» знать вовсе и не обязательно. См. например как это сделано в gcc.
          • +1
            Почитайте про такую штуку как segmented stacks.
            • +1
              Знаю. И по-прежнему остаётся открытый вопрос о поимке ограничения.
        • +2
          Для тех, кто программировал на ассемблере, ненадёжность рекурсии является очевидной.
        • +3
          «Recursion is the GOTO of functional programming»

          Erik Meijer.
          По моему опыты циклы и особенно map/fold часто читаемее, рекурсии для обработки коллекций.
          • +1
            Эээ… А зачем рекурсия для обработки коллекций?
            • +7
              Как это зачем? Для обработки коллекций коллекций коллекций.
              • 0
                Википедия говорит, что «Коллекции отличаются от контейнеров тем, что допускают ветвистую структуру». А где ветки — там и рекурсия.
            • –5
              Рекурсия: см. рекурсия.

              Это не рекурсия, а бесконечный цикл.
              • +6
                Только при наличии tail-recursion optimization.
              • +2
                К сожалению, Python не оптимизирует tail рекурсию — поэтому, считаю что на Python писать рекурсивные алгоритмы для прод систем не стоит.
                Слова Гвидо на эту тему.
                • +2
                  В моём личном восприятии вселенной, польза от tail recursion optimization наличенствует только в функциональных языках без циклов для имитации этих самых циклов.
                  Во всех остальных случаях слишком легко малейшим изменением ТЗ сломать эту самую Tail рекурсию.
                  И тогда приходится изворачиваться и расшиперивать состояние, которое тащишь за собой через всю рекурсию, чтобы сохранить tail'овость.
                  Уж лучше просто избавиться от рекурсии и написать цикл явно.
                  • 0
                    Разделяю с вами ваше восприятие вселенной.
                    Одна из причин почему в Python нет tail recursion optimisation — невозможность иметь нормальный stack trace. В том же Erlang исследовать падение рекурсивной функции через stack trace еще то удовольствие.
                • +2
                  Последний раз когда использовал рекурсию, решал NP задачку на графах и не рекурсивного алгоритма с ходу не придумал.
                  • 0
                    Хороший повод выложить условие задачи и, возможно, решение, чтобы обезрекурсить её?
                    • 0
                      Задача: дан граф телефонной сети оператора. Узлы гафа АТС, ребра канал связи с которого можно собирать сигнальный трафик. Необходимо построить минимальное покрытие ребер, накрывающее все пути в графе.

                      Т.к. тех. директор отложил на неопределенное время, то дальше рабочего рекурсивного алгоритма не ушло.
                      • 0
                        А можно уточнить, все пути в графе, в смысле кратчайшие пути между всеми парами вершин? В такой формулировке придется всегда брать все ребра графа в покрытие, потому что каждое ребро есть кратчайший путь между двумя вершинами. Или граф взвешенный? Или покрыть надо пути между какими-то особыми вершинами?
                        • +2
                          Подождите, а чем это отличается от минимального остовного (покрывающего) дерева? Насколько я помню, в Кормане вполне себе дается итеративное решение задачи.
                          • 0
                            Особенность предметной области:
                            — статическая маршрутизация;
                            — балансировка каналов связи;
                            — аварии на каналах связи.

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

                            • 0
                              Попробуйте ещё какую-нибудь хорошую метаэвристику типа Harmony Search, раз такой ад.
                          • 0
                            В любом случае, всегда можно попробовать эмулировать рекурсию: создать стек в куче и складывать туда старые значения переменных вместо ухода в глубь рекурсии. Это попрежнему будет есть память, но, по крайней мере, это будет память кучи а не стека.
                            • +1
                              Легко сказать, сложно сделать, да и зачем? Наша компания зарабатывает за счет оказания тех поддержки, поэтому нам известны графы реальных сетей и в них нет какого то гигантского количества вершин и ребер. ПО крутится на серверах под GLU/Linux и мы всегда можем расширить стек.
                          • –1
                            Допустим, вот вам массив точек на двухмерной плоскости, у каждой точки соответственно 2 вещественные координаты. Они более менее все случайно сгенерированы. Нужно найти треугольник из точек наименьшей площади. Рекурсивно это делается как 2 пальца, а вот как циклами это сделать?
                            • 0
                              Рекурсивно как два пальца вы получите stack overflow. А с циклами это делается элементарно: создаём стек с нужными нам характеристиками и бегаем по массиву циклами. При этом, в качестве бонуса, мы получаем отсутствие необходимости пробрасывать состояния между вызовами функций и в любой момент можем легко посмотреть полное состояние стека.
                          • +1
                            Любая рекурсия может быть сведена к итерации над стеком (структурой данных). На практике так получаются более экономичные (в смысле потребления памяти) решения.
                            • 0
                              Но еще есть немало алгоритмов, которые просто имеют нерекурсивный аналог, более эффективный.

                              … хотя поиск оптимального пути в графе по-моему все же «лобовая» задача.
                              • 0
                                А как это вы свели задачу к поиску оптимального пути?
                                • +1
                                  После уточнений вверху это уже не оптимальный путь. Я пока вообще не понимаю задачу, поэтому жду еще уточнений :)
                          • +2
                            Рекурсия, по сути, это доказательство по индукции

                            Это утверждение неточно и вводит в заблуждение.

                            Рекурсия это сведение задачи сложности N к (N-1)
                            Например факториал F(N) = N * F(N-1)

                            Индукция это метод математического доказательства из двух этапов.
                            1. доказательство для базы ( обычно 1)
                            2. доказательство истинности для (N+1) при условии истинности для N

                            Насколько мне известно, любой рекурсивный алгоритм можно свести к нерекурсивному (но это не всегда просто ). Алгоритмы рекурсивные и нерекурсивные — разные алгоритмы.
                            Зачастую рекурсивные алгоритмы значительно элегантнее и проще для понимания, но в большинстве задач реализовывать надо стараться нерекурсивные.
                            С моей точки зрения рекурсия хороша в декларативных языках ( Лисп и т.д. )
                            • 0
                              Если поменять в индукции второй шаг на «доказательство истинности для N при условии истинности для N-1» отличие становится только косметическим. Или я делаю ту же ошибку, что и тонны других людей: неправильно понимаю, но при этом использую…
                              • +1
                                процитирую ВИКИПЕДИЮ

                                Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

                                Математическая индукция — метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.

                                если вы считаете что по существу это одно и тоже ( метод доказательства = описанию ), то что лишнее?
                                ссылаться на других людей несколько некорректно, поскольку вы автор и отвечаете за свои слова.
                                • 0
                                  В статье я говорю не о Рекурсивном Описании чего бы то ни было, а о Рекурсивных Алгоритмах, цель которых — решение задачи через решение аналогичных исходной подзадач.
                                  Индуктивное доказательство 1-в-1 записывается в рекурсивной имплементации, именно в этой точки они и являются единым целым, именно о том, что не стоит использовать подобные наивные реализация и написана вся статья.
                                  • 0
                                    Чем отличается рекурсивный алгоритм от рекурсивного описания?
                                    • –1
                                      Алгоритм ≈ описание последовательности действий.
                                      Для меня индукция это доказательство путем предоставления рекурсивного алгоритма.
                                      То есть мы доказываем истинность на практике — вот так оно решается, а значит, доказано.

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

                                        если мы оба ведем речь о Математической индукции ( а не о электромагнитной, например ), то вы без какой либо необходимости переопределяете ее. Ваше мнение расходится с общепринятым.
                                        • 0
                                          «Индукция это метод математического доказательства из двух этапов.
                                          1. доказательство для базы ( обычно 1)
                                          2. доказательство истинности для (N+1) при условии истинности для N»

                                          Рекурсия:
                                          определяем шаг N через шаги для N-1
                                          определяем базу.

                                          где разница-то?
                                          • –1
                                            Индукция это доказательство из двух этапов

                                            Рекурсия это сведение (многократная редукция) задачи сложности N к (N-1) и далее
                                            (N-1) к (N-2)
                                            (N-2) к (N-3)

                                            3 к 2
                                            2 к 1

                                            Выполняется (N-1) раз

                                            Если вы не видите разницу между двумя разными понятиями, то я вам ничем не могу помочь.
                                            • –1
                                              Рекурсивный алгоритм записывается строго в том же виде, как и индуктивное доказательство.
                                              Мы показываем как свести N к (N-1)
                                              Мы говорим что делать при N=0 или N=1 или что там за базу.

                                              То, что _выполняется_ оно все эти разы это уже другой вопрос.
                                              В коде пишется строго сведение N к N-1 и поведение при базе.

                                              Если вы не видите тут ничего общего, что ж, да, вы ничем не можете помочь.
                            • –2
                              У меня с некоторых пор есть яркий пример (по-мимо канонических и всем известных) где не надо использовать рекурсию, или если и использовать, то хвостовую.
                              Человек, выше меня по должности написал
                              вот так:
                                       public static void Reverse<T>(this LinkedList<T> list) {
                                          list.Head = Reverse(list.Head);
                                      }
                              
                                      private static LinkedList<T>.Node Reverse<T>(LinkedList<T>.Node node) {
                                          if(node == null)
                                              return null;
                              
                                          if(node.Next == null)
                                              return node;
                              
                                          var next = node.Next;
                                          node.Next = null;
                              
                                          var result = Reverse(next);
                                          next.Next = node;
                              
                                          return result;
                                      }

                              А я переписал это на
                              это
                                      public static void Reverse<T>(this LinkedList<T> list) {
                                          if(list.Head == null)
                                              return;
                              
                                          LinkedList<T>.Node first = list.Head;
                                          LinkedList<T>.Node last = first;
                                          LinkedList<T>.Node current = last.Next;
                                          while(current != null) {
                                              last.Next = current.Next;
                                              current.Next = first;
                                              first = current;
                                              current = last.Next;
                                          }
                                          list.Head = first;
                                      }
                              


                              Второй вариант позволяет обрабатывать связные списки с длиной более 60000 элементов и работает в трое быстрее то, что был изначально. Без замеров скорости мне не верили что я прав.
                              • +9
                                Не очень понял, для кого рассчитана эта статья. На мой взгляд, новичок ничего не поймет (хотя бы потому, что нет четкого определения).
                                Для знакомого с рекурсией — зачем пример про обход дерева и числа фибонначи? Это же элементарно.
                                Про хвостовую рекурсию — ни слова
                                Множественная рекурсия, косвенная рекурсия — тоже не слышал.

                                Основная донесенная мысль, как я понял — рекурсия вредна, т.к.
                                1) внезапно может закончится стек и все сломается
                                2) есть более оптимальные нерекурсивные алгоритмы

                                Использование своего стека вместо стека вызовов — замечательно, только вот он тоже конечный и тоже может внезапно кончиться. Если подразумевается контролирование глубины рекурсии, не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.

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

                                Рекурсия зачастую существенно поднимает читаемость кода. Время программиста сейчас дороже, чем время процессора.

                                Мой пример задачи, которую муторно решать нерекурсивно — deepCopy для json, где в зависимости от типа object/array/primitive вызываются разные методы (пример косвенной и множественной рекурсии кстати).

                                • –2
                                  > не вижу проблемы передавать параметр глубины в рекурсивный вызов и делать проверку.
                                  Удачи протащить этот параметр через косвенную и множественную рекурсию, кстати ;) И учесть хвостовую.
                                  • +3
                                    На хвостовую это не должно влиять. В чем именно заключается проблема протаскивания через косвенную и множественную?
                                    • 0
                                      Проблема заключается в первую и основную очередь в том, что из абстракции начинают торчать уши реализации.
                                      Причем торчать самым неприятным образом.

                                      А еще максимальная глубина может зависеть от того, через какой из конкретных имплементаций шага проходит (в языках, где размер фрейма зависит от локальных переменных).
                                      • 0
                                        Позвольте тогда поинтересоваться, что в вашем понимании тогда «торчание ушей реализации» и как они не будут торчать в итеративной реализации.

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

                                        Насчет максимальной глубины — да, зависит. А вы количество циклов ( размер стека) тоже ограничиваете в зависимости от сложности конкретного участка кода? Или выбираете какое-то разумное ограничение, которое не должно зависеть от реализации?
                                        • 0
                                          По ограничениям позже. Это вообще скользкая дорожка где нет одного идеального решения.

                                          А про торчание ушей — нет универсального рецепта, но таскание дополнительного параметра, который должны учитывать или как минимум не терять вторичные функции (в том числе, определяемые пользователем) это неприятно.
                                          • 0
                                            Где таскание? В пользовательском коде? Этого можно избежать, и я сказал как. В коде функции? Два места — проверка (которая будет и в итеративном коде) и рекурсивный вызов (в итеративном подходе у вас будет инкремент счетчика ну или хотя бы декларация цикла).

                                            О ужас, один лишний параметр. У вас этот «лишний» — счетчик. Там где напрашивается рекурсия, рекурсивный код будет компактнее (ваши же примеры это подтверждают) и, скорее всего, в нем будет меньше сущностей. Насчет этого я, надеюсь, вы согласитесь.
                                    • +2
                                      А зачем в хвостовую рекурсию протаскивать глубину, если она будет развёрнута? Если же она развёрнута не будет — то и дополнительный индекс ни на что, кроме максимальной глубины, не повлияет.
                                      • 0
                                        А вы всегда знаете, будет ли ваша рекурсия развернута?
                                        А в отладочном билде? А на новой версии компилятора?
                                        • 0
                                          Если вы не знаете, будет ли развёрнута рекурсия — проще развернуть сразу вручную. Благо делается это тривиально: оборачиваем всё в цикл и перезаписываем значения переменных новыми в конце итерации.
                                          • +1
                                            Вот об этом я и пишу.
                                            • 0
                                              В этой ветке речь шла не о том, а о трудностях передачи уровня рекурсии в рекурсивную функцию.
                                              И передавать параметр в хвостовую рекурсию не я собирался :P
                                              Я просто обращаю внимание на то, что этот аргумент не состоятелен, так как такой тип рекурсии легче всех прочих раскрыть вручную. Не касаясь других типов рекурсии.
                                  • –1
                                    Не смог уйти дальше первой строки топика.(( Расскажи кратко, в чём же суть?
                                    • –1
                                      Да, не все могут в юмор. Статистика: примерно 2 трети юмор не могут.
                                    • 0
                                      В языке Scheme хвостовая рекурсия — кажется, единственный способ организовать цикл.
                                      Помню, мучился, когда делал скрипт для Gimp, для массового применения набора фильтров к изображениям.
                                      • 0
                                        То же и в Erlang.
                                        Но вообще, правильное решение — пользуйте fold'ы :)
                                        • 0
                                          Fold в Erlang тоже не всегда применим, особенно когда у вас вложенные fold с ветвистой логикой. Tail рекурсия в данном случае выглядит гораздо чище.
                                      • +1
                                        Ну упадёт воркер обрабатывающий запрос хакера — ничего страшного. Куда хуже, если он будет бесконечно крутиться в цикле, раздувая кучу. Избавляться от рекурсии нужно только если в штатной ситуации надо обрабатывать глубокие деревья, но это очень специфические случаи.

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