Способ перехода от рекурсии к итерации
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
За многие годы программирования я довольно часто использовал рекурсию для решения простых задач, но я полностью осознаю, что иногда вам нужна итерация из-за проблем с памятью/скоростью.
Итак, когда-то в очень далеком прошлом я попытался выяснить, существует ли какой-либо «шаблон» или учебниковый способ преобразования обычного рекурсивного подхода в итерацию, и ничего не нашел.Или, по крайней мере, ничто из того, что я помню, не помогло бы.
- Есть ли общие правила?
- Есть ли «шаблон»?
Решение
Обычно я заменяю рекурсивный алгоритм итеративным алгоритмом, помещая в стек параметры, которые обычно передаются в рекурсивную функцию.По сути, вы заменяете стек программ на свой.
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);
Редактировать:Статья Стеки и устранение рекурсии (или Резервная копия статьи) более подробно рассказывает об этом.
Другие советы
На самом деле, самый распространенный способ сделать это — сохранить свой собственный стек.Вот рекурсивная функция быстрой сортировки в 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 представляет собой трехмерное дерево с указателями 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++ (если бы не использование аргумента по умолчанию):
// 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).
Но если мы используем стек, сложность остается той же.Я думаю, что только хвостовую рекурсию можно преобразовать в итерацию.
А устранение стеков и рекурсии В статье отражена идея экстернализации кадра стека в куче, но не приводится простой и повторяемый способ конвертации.Ниже один.
При преобразовании в итеративный код необходимо учитывать, что рекурсивный вызов может произойти из блока кода произвольной глубины.Важны не только параметры, но и точка возврата к логике, которую еще предстоит выполнить, и состояние переменных, которые участвуют в последующих условных выражениях.Ниже приведен очень простой способ преобразования в итеративный код с наименьшими изменениями.
Рассмотрим этот рекурсивный код:
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);
}
}
Обычно метод предотвращения переполнения стека для рекурсивных функций называется методом батута, который широко применяется разработчиками 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);
}
Думая о вещах, которым действительно нужен стек:
Если мы рассмотрим шаблон рекурсии как:
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, но это может быть полезно, поскольку у вас есть больше контроля над ней.
Один из шаблонов, на который следует обратить внимание, — это вызов рекурсии в конце функции (так называемая хвостовая рекурсия).Это можно легко заменить на некоторое время.Например, функция 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;
}
}
что исключает второй рекурсивный вызов.
Я только что проголосовал за ответ, предлагающий использовать явный стек, который, по моему мнению, является правильным решением и имеет общую применимость.
Я имею в виду, что вы можете использовать его для преобразования любой рекурсивной функции в итеративную функцию.Просто проверьте, какие значения сохраняются при рекурсивных вызовах, это те, которые иметь быть локальным по отношению к рекурсивной функции, и замените вызовы циклом, в котором вы поместите их в стек.Если стек пуст, рекурсивная функция будет завершена.
Я не могу удержаться и сказать, что доказательство того, что каждая рекурсивная функция эквивалентна итеративной функции для другого типа данных, является одним из моих самых дорогих воспоминаний об университетских временах.Именно этот курс (и профессор) действительно помог мне понять, что такое компьютерное программирование.
А вопрос который был закрыт как дубликат этого, имел очень специфическую структуру данных:
Узел имел следующую структуру:
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 с детерминированным топологическим упорядочением.Текущие дочерние узлы переставляются так, что последний дочерний элемент усыновляет всех остальных дочерних узлов.Затем текущий узел можно удалить, а затем выполнить обход до оставшегося дочернего узла.
Рекурсия - это не что иное, как процесс вызова одной функции из другой, только этот процесс выполняется путем вызова функции самой по себе.Как мы знаем, когда одна функция вызывает другую функцию, первая функция сохраняет свое состояние (свои переменные), а затем передает управление вызываемой функции.Вызываемая функция может быть вызвана с использованием тех же имен переменных, например, fun1(a) может вызывать fun2(a).Когда мы выполняем рекурсивный вызов, ничего нового не происходит.Одна функция вызывает сама себя, передавая себе переменные одного и того же типа и схожие по имени (но, очевидно, значения, хранящиеся в переменных, разные, только имя остается прежним).Но перед каждым вызовом функция сохраняет свое состояние и этот процесс сохранения продолжается.СОХРАНЕНИЕ ПРОИЗВОДИТСЯ В СТЕКЕ.
ТЕПЕРЬ В ИГРУ ВХОДИТ СТЕК.
Итак, если вы пишете итеративную программу и каждый раз сохраняете состояние в стеке, а затем извлекаете значения из стека, когда это необходимо, вы успешно преобразуете рекурсивную программу в итеративную!
Доказательство простое и аналитическое.
В рекурсивном режиме компьютер поддерживает стек, а в итеративной версии вам придется поддерживать стек вручную.
Подумайте об этом, просто преобразуйте рекурсивную программу поиска в глубину (на графиках) в итеративную программу dfs.
Всего наилучшего!
Примерное описание того, как система берет любую рекурсивную функцию и выполняет ее с помощью стека:
Это было сделано для того, чтобы показать идею без подробностей.Рассмотрим эту функцию, которая распечатывает узлы графа:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
Например график:A-> b a-> c show (a) печатать b, a, c
Вызовы функций означают сохранение локального состояния и точки продолжения, чтобы вы могли вернуться, а затем перейти к функции, которую хотите вызвать.
Например, предположим, что show(A) начинает работать.Вызов функции в строке 3.Show (b) eade - добавьте элемент в стек, что означает «Вам нужно продолжить в строке 2 с локальным узлом состояния переменной = a» - goto line 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;
}
