Путь от рекурсии к итерации

действительно, самый распространенный способ сделать это-сохранить свой собственный стек. Вот рекурсивная функция quicksort в 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;
    }
}

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

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

Я только что придумал пример 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();
            }


        }

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

ну, в общем, рекурсию можно имитировать как итерацию, просто используя переменную хранения. Обратите внимание, что рекурсия и итерация, как правило, эквивалентны; один почти всегда может быть преобразован в другой. Хвостовая рекурсивная функция очень легко преобразуется в итеративную. Просто сделайте переменную аккумулятора локальной и повторите вместо рекурсии. Вот пример в 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;
}

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

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

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

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

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

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

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

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();
    }

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

}

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

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

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);
    }

}

вообще метод, чтобы избежать переполнения стека для рекурсивных функций называется trampoline метод, который широко принят 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);
}

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;
     }
}

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

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

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

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

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

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

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;
    }
}

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

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

ТЕПЕРЬ СТЕК ВСТУПАЕТ В ИГРУ.

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

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

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

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

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

думая о вещах, которые на самом деле нуждаются в стеке:

если рассматривать шаблон рекурсии как:

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, но это может быть полезно в том, что у вас больше контроля над ним.

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

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

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

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

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

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

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

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

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

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

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

#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;
}