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

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

Edit: в статье Stacks and Recursion Elimination (или Article Backup link) переходит в более подробную информацию по этому вопросу.

Answer 2

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

Answer 3

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

Answer 4

Один шаблон для поиска - это вызов рекурсии в конце функции (так называемая хвостовая рекурсия). Это можно легко заменить на некоторое время. Например, функция 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; 
    } 
} 

, который устраняет второй рекурсивный вызов.

Answer 5

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

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

Answer 6

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

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

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

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

Answer 8

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

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

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

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

Кажется, никто не обратился, где рекурсивная функция вызывает себя больше, чем когда-то в теле, и обращается к определенной точке рекурсии (т. е. не примитивно-рекурсивной). Говорят, что это every recursion can be turned into iteration, поэтому кажется, что это должно быть возможно.

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

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

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

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

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

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

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

Все самое лучшее!

Answer 12

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

Однако для C# существует небольшой вспомогательный метод here, который превращает вашу рекурсивную функцию в итеративный, не требуя изменения логики или сделать код понятным. 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); 
} 

Answer 13

stacks and recursion elimination статья отражает идею экспортирования стека на куче, но не обеспечивает простых и повторяемый способа конвертировать. Ниже - один.

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

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

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 14

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

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

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

Например графа: А-> В А-> С шоу (А) будет печатать B, A, C

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

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

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

Answer 15

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

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

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

Answer 16

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

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

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

Answer 17

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

Если мы рассмотрим образец рекурсии как:

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

Answer 18

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