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

Question

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

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

• Существуют ли общие правила?
• Есть ли "шаблон"?

Answer 1

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

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

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

foo(first);
foo(second);

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

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

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

Answer 2

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

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

Answer 3

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

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


        }

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

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

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

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

}

Answer 8

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

Answer 9

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

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

}

Answer 10

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