Посещение древовидной или графической структуры с использованием хвостовой рекурсии - PullRequest
Новая
       10

Посещение древовидной или графической структуры с использованием хвостовой рекурсии

4 голосов
/ 23 января 2012

Допустим, у меня есть структура для посещения рекурсивным способом.

Псевдокод: 

visit(node n)
{
    if (n == visited)
         return;

    //do something
    setVisited(n);
    foreach child_node in n.getChildren(){
        visit(child_node);
    }

}

В соответствии с этим поток рекурсия хвоста может произойти, когда:

Хвостовая рекурсия в основном, когда:

  • существует только один рекурсивный вызов
  • , который является последним оператором в функции

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

Мой вопрос:

Есть ли способ реорганизовать приведенный выше код, чтобы сделать его хвостовым рекурсивным?Я ищу решение, которое не удаляет рекурсию, если она есть (например, я не хочу использовать стек для имитации рекурсии и преобразования его в итеративную функцию).

это возможно?

Если язык уместен, я использую C ++.

Ответы [ 3 ]

2 голосов
/ 23 января 2012

Хвостовая рекурсия имитирует циклы без стека [или любой другой структуры данных], т. Е. O(1) дополнительное пространство.

AFAIK, рассматриваемая проблема обхода дерева / графа [предположим, нет parent поля в каждом узле], не может быть выполнена с такой сложностью [O(n) время, O(1) пространство], поэтому не может быть выполнена с помощью один цикл, без стека. Следовательно, рефакторинг хвостовой рекурсии невозможен.

РЕДАКТИРОВАТЬ: Проблема может быть решена в O (1) пространстве, но с O (n ^ 2) времени [который является двойной петлей], как видно в этот пост .

2 голосов
/ 23 августа 2017

Таким образом, на самом деле вы можете всегда рефакторировать функцию, чтобы она была хвостовой рекурсивной ... Большинство людей, программирующих на других языках, будут использовать продолжение для его эффективного кодирования. Но мы смотрим здесь на язык C / C ++ более конкретно, поэтому я предполагаю избавиться от этого, просто кодируя саму функцию (я имею в виду, не добавляя в язык универсальную инфраструктуру продолжения).

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

void iterative() {
  while (cond)
    dosomething()
}

Затем, чтобы превратить его в хвостовую рекурсивную функцию, достаточно написать: 

void tailrecursive() {
  if (!cond)
    return;

  dosomething();
  tailrecursive();
}

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

void recursive_preorder(node n) {
  if (n == visited)
    return;

  dosomething(n);
  foreach child_node in n.getChildren() {
    recursive_preorder(child_node);
  }
}

Итеративному эквиваленту необходим ввод стека для запоминания узлов проводника (поэтому мы добавляем операции push / pop): 

void iterative_preorder(node n) {
  if (n == visited)
    return;

  stack worklist = stack().push(n);
  while (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
}

Теперь, взяв эту итеративную версию обхода дерева предзаказов и превратив ее в хвостовую рекурсивную функцию, получим: 

void tail_recursive_preorder_rec(stack worklist) {
  if (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
  tail_recursive_preorder_rec(worklist)
}

void tail_recursive_preorder (node n) {
  stack worklist = stack().push(n);
  tail_recursive_preorder_rec(worklist);
}

И это дает вам хвостовую рекурсивную функцию, которая будет приятно оптимизирована компилятором. Наслаждайтесь!

2 голосов
/ 23 января 2012

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

Я не могу придумать, как изменить алгоритм, чтобы сделать его хвостово-рекурсивным - у вас всегда будет такой потенциал для нескольких детей, который его испортит.

...