Способ перехода от рекурсии к итерации

Стремитесь сделать ваш рекурсивный вызов Рекурсия хвоста (рекурсия, где последний оператор является рекурсивным вызовом). Как только у вас есть это, преобразовать его в итерацию, как правило, довольно просто.

Выполните поиск в Google по запросу "Продолжение прохождения". Существует общая процедура преобразования в хвостовой рекурсивный стиль; существует также общая процедура преобразования хвостовых рекурсивных функций в циклы.

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

void foo(Node* node)
{
    if (node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

заканчивается вызовом foo. Его можно заменить на:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

что исключает второй рекурсивный вызов.

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

// tail-recursive
int factorial (int n, int acc = 1)
{
  if (n == 1)
    return acc;
  else
    return factorial(n - 1, acc * n);
}

// iterative
int factorial (int n)
{
  int acc = 1;
  for (; n > 1; --n)
    acc *= n;
  return acc;
}

Зная меня, я, наверное, ошибся в коде, но идея есть.

На самом деле, наиболее распространенный способ сделать это - сохранить свой собственный стек. Вот рекурсивная функция быстрой сортировки в C:

void quicksort(int* array, int left, int right)
{
    if (left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

Вот как мы можем сделать его итеративным, сохранив собственный стек:

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

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

Обычно я заменяю рекурсивный алгоритм итерационным алгоритмом, помещая в стек параметры, которые обычно передаются рекурсивной функции. Фактически, вы заменяете программный стек на свой собственный.

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

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

foo(first);
foo(second);

должен быть заменен на

stack.push(second);
stack.push(first);

Обновлено: статья Стеки и устранение рекурсии (или Ссылка на резервную копию статьи) дает более подробную информацию по этому вопросу.

Даже использование стека не преобразует рекурсивный алгоритм в итеративный. Обычная рекурсия - это рекурсия на основе функций, и если мы используем стек, то она становится рекурсией на основе стека. Но это все еще рекурсия.

Для рекурсивных алгоритмов пространственная сложность составляет O (N), а временная сложность - O (N). Для итерационных алгоритмов пространственная сложность составляет O (1), а временная сложность - O (N).

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

Просто убиваю время ... Рекурсивная функция

void foo(Node* node)
{
    if (node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

можно преобразовать в

void foo(Node* node)
{
    if (node == NULL)
       return;

    // Do something with node...

    stack.push(node->right);
    stack.push(node->left);

    while(!stack.empty()) {
         node1 = stack.pop();
         if (node1 == NULL)
            continue;
         // Do something with node1...
         stack.push(node1->right);             
         stack.push(node1->left);
    }

}

Кажется, никто не обратился к тому, где рекурсивная функция вызывает себя более одного раза в теле и обрабатывает возврат к определенной точке рекурсии (т.е. не примитивно-рекурсивной). Говорят, что каждую рекурсию можно превратить в итерацию, поэтому кажется, что это должно быть возможно.

Я только что придумал пример на C# того, как это сделать. Предположим, у вас есть следующая рекурсивная функция, которая действует как обход по порядку, и что AbcTreeNode - это 3-арное дерево с указателями a, b, c.

public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
        if (x != null) {
            AbcRecursiveTraversal(x.a, list);
            AbcRecursiveTraversal(x.b, list);
            AbcRecursiveTraversal(x.c, list);
            list.Add(x.key);//finally visit root
        }
}

Итерационное решение:

        int? address = null;
        AbcTreeNode x = null;
        x = root;
        address = A;
        stack.Push(x);
        stack.Push(null)    

        while (stack.Count > 0) {
            bool @return = x == null;

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


            if (@return == true) {
                address = (int?)stack.Pop();
                x = (AbcTreeNode)stack.Pop();
            }


        }

Рекурсия - это не что иное, как процесс вызова одной функции из другой, только этот процесс выполняется путем вызова самой функции. Как мы знаем, когда одна функция вызывает другую, первая функция сохраняет свое состояние (свои переменные), а затем передает управление вызываемой функции. Вызываемая функция может быть вызвана с использованием того же имени переменных, что ex fun1 (a) может вызывать fun2 (a). Когда мы выполняем рекурсивный вызов, ничего нового не происходит. Одна функция вызывает себя, передавая один и тот же тип и похожие по именам переменные (но, очевидно, значения, хранящиеся в переменных, разные, остается только имя) самой себе. Но перед каждым вызовом функция сохраняет свое состояние, и этот процесс сохранения продолжается. ЭКОНОМИЯ СДЕЛАНА НА СТЕКЕ.

ТЕПЕРЬ СТЕК ПРИХОДИТ В ИГРУ.

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

Доказательство простое и аналитическое.

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

Подумайте над этим, просто преобразуйте рекурсивную программу поиска в глубину (на графах) в итеративную программу dfs.

Всего наилучшего!

Обычно метод предотвращения переполнения стека для рекурсивных функций называется методом трамплина, который широко применяется разработчиками Java.

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

Он работает, оборачивая части метода вспомогательным методом. Например, следующая рекурсивная функция:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Превращается в:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

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

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

Рассмотрим этот рекурсивный код:

struct tnode
{
    tnode(int n) : data(n), left(0), right(0) {}
    tnode *left, *right;
    int data;
};

void insertnode_recur(tnode *node, int num)
{
    if (node->data <= num)
    {
        if (node->right == NULL)
            node->right = new tnode(num);
        else
            insertnode(node->right, num);
    }
    else
    {
        if (node->left == NULL)
            node->left = new tnode(num);
        else
            insertnode(node->left, num);
    }    
}

Итерационный код:

// Identify the stack variables that need to be preserved across stack 
// invocations, that is, across iterations and wrap them in an object
struct stackitem 
{ 
    stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
    tnode *node; int num;
    int ra; //to point of return
};

void insertnode_iter(tnode *node, int num) 
{
    vector<stackitem> v;
    //pushing a stackitem is equivalent to making a recursive call.
    v.push_back(stackitem(node, num));

    while(v.size()) 
    {
        // taking a modifiable reference to the stack item makes prepending 
        // 'si.' to auto variables in recursive logic suffice
        // e.g., instead of num, replace with si.num.
        stackitem &si = v.back(); 
        switch(si.ra)
        {
        // this jump simulates resuming execution after return from recursive 
        // call 
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

        if (si.node->data <= si.num)
        {
            if (si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {
                // replace a recursive call with below statements
                // (a) save return point, 
                // (b) push stack item with new stackitem, 
                // (c) continue statement to make loop pick up and start 
                //    processing new stack item, 
                // (d) a return point label
                // (e) optional semi-colon, if resume point is an end 
                // of a block.

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;         
            }
        }
        else
        {
            if (si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {
                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;
            }
        }

        v.pop_back();
    }
}

Обратите внимание, что структура кода по-прежнему соответствует рекурсивной логике, а модификации минимальны, что приводит к меньшему количеству ошибок. Для сравнения я обозначил изменения ++ и -. Большинство новых вставленных блоков, кроме v.push_back, являются общими для любой преобразованной итеративной логики.

void insertnode_iter(tnode *node, int num) 
{

+++++++++++++++++++++++++

    vector<stackitem> v;
    v.push_back(stackitem(node, num));

    while(v.size())
    {
        stackitem &si = v.back(); 
        switch(si.ra)
        {
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

------------------------

        if (si.node->data <= si.num)
        {
            if (si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;    

-------------------------

            }
        }
        else
        {
            if (si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;

-------------------------

            }
        }

+++++++++++++++++++++++++

        v.pop_back();
    }

-------------------------

}

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

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

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

Например график: А-> В А-> С show (A) напечатает B, A, C

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

Например, предположим, что шоу (A) начинает работать. Вызов функции в строке 3. show (B) означает - Добавить элемент в стек, означающий, что «вам нужно будет продолжить со строки 2 с локальным состоянием переменной node = A». - Перейти к строке 0 с node = B.

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

Этот связь дает некоторое объяснение и предлагает идею сохранения «местоположения», чтобы иметь возможность попасть в точное место между несколькими рекурсивными вызовами:

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

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}

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

Узел имел следующую структуру:

typedef struct {
    int32_t type;
    int32_t valueint;
    double  valuedouble;
    struct  cNODE *next;
    struct  cNODE *prev;
    struct  cNODE *child;
} cNODE;

Функция рекурсивного удаления выглядела так:

void cNODE_Delete(cNODE *c) {
    cNODE*next;
    while (c) {
        next=c->next;
        if (c->child) { 
          cNODE_Delete(c->child)
        }
        free(c);
        c=next;
    }
}

В общем, не всегда можно избежать стека для рекурсивных функций, которые вызывают себя более одного раза (или даже один раз). Однако для этой конкретной конструкции это возможно. Идея состоит в том, чтобы объединить все узлы в единый список. Это достигается путем помещения child текущего узла в конец списка верхней строки.

void cNODE_Delete (cNODE *c) {
    cNODE *tmp, *last = c;
    while (c) {
        while (last->next) {
            last = last->next;   /* find last */
        }
        if ((tmp = c->child)) {
            c->child = NULL;     /* append child to last */
            last->next = tmp;
            tmp->prev = last;
        }
        tmp = c->next;           /* remove current */
        free(c);
        c = tmp;
    }
}

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

Подумайте о вещах, которым действительно нужен стек:

Если мы рассмотрим схему рекурсии как:

if (task can be done directly) {
    return result of doing task directly
} else {
    split task into two or more parts
    solve for each part (possibly by recursing)
    return result constructed by combining these solutions
}

Например, классическая Ханойская башня.

if (the number of discs to move is 1) {
    just move it
} else {
    move n-1 discs to the spare peg
    move the remaining disc to the target peg
    move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}

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

place seed task on stack
while stack is not empty 
   take a task off the stack
   if (task can be done directly) {
      Do it
   } else {
      Split task into two or more parts
      Place task to consolidate results on stack
      Place each task on stack
   }
}

Для Ханойской башни это становится:

stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
    task = stack.pop();
    if (task.size() = 1) {
        just move it
    } else {
        stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
        stack.push(new Task(1, task.from(), task.to(), task.spare()));
        stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
    }
}

Здесь есть значительная гибкость в том, как вы определяете свой стек. Вы можете сделать свой стек списком объектов Command, которые выполняют сложные задачи. Или вы можете пойти в противоположном направлении и составить список более простых типов (например, «задача» может состоять из 4 элементов в стеке int, а не одного элемента в стеке Task).

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

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

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

#include <iostream>
#include <stack>
using namespace std;

int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }

struct Par
{
    int a, b;
    Par() : Par(0, 0) {}
    Par(int _a, int _b) : a(_a), b(_b) {}
};

int GCDIter(int a, int b)
{
    stack<Par> rcstack;

    if (b == 0)
        return a;
    rcstack.push(Par(b, a % b));

    Par p;
    while (!rcstack.empty()) 
    {
        p = rcstack.top();
        rcstack.pop();
        if (p.b == 0)
            continue;
        rcstack.push(Par(p.b, p.a % p.b));
    }

    return p.a;
}

int main()
{
    //cout << GCD(24, 36) << endl;
    cout << GCDIter(81, 36) << endl;

    cin.get();
    return 0;
}

Мои примеры написаны на Clojure, но их довольно легко перевести на любой язык.

Учитывая эту функцию, StackOverflows для больших значений n:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

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

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

где return определяется как:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

Это работает и для более сложных функций, например функция Аккермана:

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

можно преобразовать в:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))