Maneira de ir de recursão para iteração
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho recursão usado bastante em meus muitos anos de programação para resolver problemas simples, mas estou plenamente consciente de que às vezes você precisa iteração devido a problemas de memória / velocidade.
Então, em algum momento no muito longe passado eu fui para tentar encontrar se existisse qualquer "padrão" ou forma livro-texto de transformar uma abordagem recursão comum a iteração e não encontrou nada. Ou pelo menos nada que me lembro ele iria ajudar.
- Existem regras gerais?
- Existe um "padrão"?
Solução
Normalmente, eu substituir um algoritmo recursivo por um algoritmo iterativo, empurrando os parâmetros que normalmente seriam passados ??para a função recursiva em uma pilha. Na verdade, você está substituindo a pilha do programa por um dos seus próprios.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
Nota: se você tiver mais de uma chamada recursiva dentro e você quer preservar a ordem das chamadas, você tem que adicioná-los na ordem inversa à pilha:
foo(first);
foo(second);
tem de ser substituído por
stack.push(second);
stack.push(first);
Edit: O artigo Pilhas e recursão Eliminação (ou artigo backup ligação ) entra em mais detalhes sobre este assunto.
Outras dicas
Realmente, a maneira mais comum de fazer isso é para manter a sua própria pilha. Aqui está uma função quicksort recursivo em 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);
}
Veja como podemos torná-lo interativo, mantendo a nossa própria pilha:
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;
}
}
Obviamente, este exemplo não verifica limites pilha ... e realmente você poderia tamanho da pilha com base no pior caso dado à esquerda e e valores corretos. Mas você começa a idéia.
Parece que ninguém abordou onde a função recursiva chama a si mesmo mais de uma vez no corpo, e alças de retornar para um ponto específico no recursão (ou seja, não primitiva recursiva). Diz-se que cada recursão pode ser transformado em iteração , por isso parece que isso deve ser possível.
Eu só veio com um exemplo C # de como fazer isso. Suponha que você tem a seguinte função recursiva, que age como um caminhamento pós-fixado, e que AbcTreeNode é uma árvore 3-ário com ponteiros 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
}
}
A solução iterativa:
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();
}
}
Esforce-se para fazer a sua chamada recursiva cauda recursão (recursão onde a última declaração é a chamada recursiva ). Uma vez que você tem isso, convertendo-a iteração é geralmente muito fácil.
Bem, em geral, a recursividade pode ser imitado como iteração simplesmente usando uma variável de armazenamento. Note-se que a recursividade e iteraction são geralmente equivalente; um quase sempre pode ser convertido para o outro. Uma função cauda-recursivo é facilmente convertido para um um iterativo. Basta fazer a variável acumulador de um local, e repita em vez de recurse. Aqui está um exemplo em C ++ (C se não fosse o uso de um argumento padrão):
// 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;
}
Conhecendo-me, eu provavelmente cometeu um erro no código, mas a ideia está lá.
Mesmo usando pilha não irá converter um algoritmo recursivo em iterativo. recursão normal é função de recursão com base e se usarmos pilha então torna-se empilhar recursão base. Mas a sua recursão ainda.
Para algoritmos recursivos, complexidade espaço é O (N) e complexidade de tempo é O (N). Para algoritmos iterativos, complexidade espaço é O (1) e complexidade de tempo é O (N).
Mas, se usarmos as coisas pilha em termos de complexidade permanece igual. Acho que só recursão de cauda pode ser convertida em iteração.
O pilhas e recursão eliminação artigo capta a ideia de externalizar o quadro de pilha no montão, mas não fornece um simples e repetível maneira de converter. Abaixo está um.
Durante a conversão ao código iterativo, é preciso estar ciente de que a chamada recursiva pode acontecer a partir de um bloco de código arbitrariamente profunda. Não são apenas os parâmetros, mas também o ponto para voltar para a lógica que continua a ser executado e o estado de variáveis ??que participam condicionais posteriores, que importa. Abaixo está uma maneira muito simples de se converter ao código iterativo com menos mudanças.
Considere este código recursiva:
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);
}
}
código iterativo:
// 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();
}
}
Observe como a estrutura do código ainda permanece fiel à lógica recursiva e modificações são mínimas, resultando em menor número de bugs. Para efeito de comparação, eu marquei as alterações com ++ e -. A maioria dos novos blocos inseridos exceto v.push_back, são comuns a qualquer lógica iterativa convertido
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();
}
-------------------------
}
pesquisa no Google por "Continuação passando estilo." Existe um procedimento geral para a conversão para um estilo recursiva cauda; há também um processo geral para transformar as funções recursivas da cauda em laços.
Apenas matando o tempo ... Uma função recursiva
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
pode ser convertido para
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);
}
}
Geralmente a técnica para evitar estouro de pilha é para funções recursivas é chamado de técnica de trampolim que é amplamente adotado pelo Java devs.
No entanto, para C # existe um método little helper aqui que transforma seu função recursiva para iterativo sem exigir a lógica mudança ou tornar o código in-compreensível. C # é uma linguagem tão boa que coisas incríveis é possível com ele.
Ele funciona envolvendo partes do método por um método auxiliar. Por exemplo, a seguinte função recursiva:
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;
}
transforma-se em:
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);
}
Pensamento de coisas que realmente precisa de uma pilha:
Se considerarmos o padrão de recursão como:
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
}
Por exemplo, a Torre clássico de Hanói
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
}
Isso pode ser traduzido em um trabalho de loop em uma pilha explícita, reafirmando-o como:
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
}
}
Para Torre de Hanói isto torna-se:
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()));
}
}
Há flexibilidade considerável aqui a respeito de como você define o seu stack. Você pode fazer sua pilha de uma lista de objetos Command que fazem coisas sofisticadas. Ou você pode ir na direção oposta e torná-lo uma lista de tipos mais simples (por exemplo, uma "tarefa" pode ser de 4 elementos em uma pilha de int, ao invés de um elemento em uma pilha de Task).
Tudo isso significa que a memória para a pilha está na pilha em vez de na pilha de execução Java, mas isso pode ser útil para que você tenha mais controle sobre ele.
Um padrão é a olhar para uma chamada recursão no final da função (assim chamada cauda-recursão). Isso pode ser facilmente substituído por um tempo. Por exemplo, a função foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
termina com uma chamada para foo. Isso pode ser substituída por:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
o que elimina a segunda chamada recursiva.
Eu só upvoted a resposta sugerindo a utilização de um pilha explícita que eu acho que é a solução certa e é de aplicação geral.
Quer dizer que você pode usá-lo para transformar qualquer função recursiva em uma função iterativa. Basta verificar que os valores são salvos através de chamadas recursivas, esses são os que Tem para ser local para a função recursiva, e substituir as chamadas com um ciclo onde você vai empurrá-los em uma pilha. Quando a pilha está vazia a função recursiva teria sido encerrado.
Eu não posso resistir a dizer que a prova de que cada função recursiva é equivalente a uma função iterativa em um tipo de dados diferente, é um dos minha memória mais querida dos meus tempos da universidade. Esse foi o curso (eo professor) que realmente me fez entender o que programação de computadores era sobre.
A questão que tinha sido fechada como uma duplicata de este tinha uma estrutura de dados muito específico:
O nó tinha a seguinte estrutura:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
A função de exclusão recursiva parecia:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
Em geral, nem sempre é possível evitar uma pilha para funções recursivas que se invocam mais de uma vez (ou mesmo uma vez). No entanto, para esta estrutura particular, é possível. A ideia é nivelar todos os nós em uma única lista. Isso é feito colocando child do nó atual no final da lista da linha superior.
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;
}
}
Esta técnica pode ser aplicada a qualquer estrutura ligada dados que podem ser reduzir ao DAG com uma ordenação topológica determinista. Os nós filhos atuais são reorganizados de modo que a última criança adota todas as outras crianças. Em seguida, o nó atual pode ser excluído e transversal pode então iterate à criança restante.
A recursão é nada, mas o processo de chamar de uma função de outro apenas neste processo é feito chamando de uma função por si só. Como sabemos quando uma função chama a outra função a primeira função salva seu estado (suas variáveis) e, em seguida, passa o controle para a função chamada. A função chamada pode ser chamado usando o mesmo nome de variáveis ??ex fun1 (a) pode chamar fun2 (a). Quando fazemos recursiva chamada nada de novo acontece. Uma função chama-se, passando o mesmo tipo e semelhante em variáveis ??nome (mas, obviamente, os valores armazenados nas variáveis ??são diferentes, apenas o nome permanece igual.) A si mesmo. Mas antes de cada chamada a função de salva seu estado e este processo de poupança continua. A ECONOMIA É FEITO EM UMA PILHA.
Agora A PILHA entra em jogo.
Então, se você escrever um programa iterativo e salvar o estado em uma pilha de cada vez e, em seguida, saem os valores da pilha, quando necessário, de ter convertido com sucesso um programa recursivo em um um iterativo!
A prova é simples e analítica.
Em recursão o computador mantém uma pilha e na versão iterativa você terá que manter manualmente a pilha.
Pense sobre ele, apenas converter uma busca em profundidade (em gráficos) programa recursivo em um programa iterativo dfs.
Tudo de bom!
Uma descrição aproximada de como um sistema assumir qualquer função recursiva e executa-lo usando uma pilha:
Esta intenção de mostrar a ideia, sem detalhes. Considere esta função que iria imprimir nós de um grafo:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
Por exemplo gráfico: A-> B A-> C show (A) iria imprimir B, A, C
As chamadas de função significa salvar o estado local e o ponto de continuação para que possa voltar, e depois saltar a função que você deseja chamar.
Por exemplo, mostrar supõem (A) começa a correr. A chamada de função na linha 3. mostra (B) meios - Adicionar item ao significado pilha "você vai precisar para continuar na linha 2 com nó estado variável local = A" -. Goto linha 0 com nó = B
Para executar o código, o sistema percorre as instruções. Quando uma chamada de função é encontrado, o empurra sistema de informação de que necessita para voltar ao que era, é executado o código de função, e quando os concluída função, aparece a informação sobre onde ele precisa ir para continuar.
Este ligação fornece uma explicação e propõe a idéia de manter "localização" para ser capaz de chegar ao lugar exato entre várias chamadas recursivas:
No entanto, todos estes exemplos descrevem cenários em que uma chamada recursiva é feito um fixa quantidade de vezes. As coisas ficam mais complicadas quando você tem algo como:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
Há uma maneira geral de converter travessia recursiva a iteração através de um iteração preguiçoso que encadeia múltiplos fornecedores iteradoras (expressão lambda que retorna uma iteração). Ver o meu Convertendo recursiva transferência para Iterator .
Um outro exemplo simples e completa de transformar a função recursiva em um iterativo usando a pilha.
#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;
}
