Caminho para ir da recursion à iteração

Eu usei recursion bastante nos meus muitos anos de programação para resolver problemas simples, mas estou plenamente ciente de que às vezes você precisa de iteração devido a problemas de memory / velocidade.

Então, em algum momento do passado, fui tentar descobrir se existia algum modo de “padrão” ou livro-texto de transformar uma abordagem de recursion comum à iteração e não encontrei nada. Ou pelo menos nada que eu possa lembrar ajudaria.

  • Existem regras gerais?
  • Existe um “padrão”?

    Geralmente, eu substituo um algoritmo recursivo por um algoritmo iterativo, empurrando os parâmetros que normalmente seriam passados ​​para a function recursiva em uma pilha. Na verdade, você está substituindo a pilha do programa por um dos seus.

    Stack 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 quiser preservar a ordem das chamadas, terá que adicioná-las na ordem inversa à pilha:

     foo(first); foo(second); 

    tem que ser substituído por

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

    Edit: O artigo Stacks and Recursion Elimination (ou link Article Backup ) entra em mais detalhes sobre este assunto.

    Realmente, a maneira mais comum de fazer isso é manter sua própria pilha. Aqui está uma function de quicksort recursiva 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 iterativo mantendo 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 de pilha … e realmente você poderia dimensionar a pilha com base no pior caso, dados os valores à esquerda e à direita. Mas você entendeu a ideia.

    Parece que ninguém abordou onde a function recursiva se chama mais de uma vez no corpo e lida com o retorno a um ponto específico na recursion (isto é, não primitivo-recursivo). Dizem que toda recursion pode ser transformada em iteração , então parece que isso deveria ser possível.

    Eu acabei de chegar com um exemplo c # de como fazer isso. Suponha que você tenha a seguinte function recursiva, que age como uma travessia de pós-ordem, e que AbcTreeNode é uma tree 3-ary com pointers a, b, c.

     public static void AbcRecursiveTraversal(this AbcTreeNode x, List list) { if (x != null) { AbcRecursiveTraversal(xa, list); AbcRecursiveTraversal(xb, list); AbcRecursiveTraversal(xc, 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 = xa; address = A; break; case B: stack.Push(x); stack.Push(C); x = xb; address = A; break; case C: stack.Push(x); stack.Push(null); x = xc; 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 sua chamada recursiva Tail Recursion (recursion onde a última instrução é a chamada recursiva). Uma vez que você tenha feito isso, convertê-lo para iteração é geralmente muito fácil.

    Bem, em geral, a recursion pode ser imitada como iteração usando simplesmente uma variável de armazenamento. Observe que recursion e iteração são geralmente equivalentes; quase sempre pode ser convertido para o outro. Uma function recursiva de cauda é facilmente convertida em iterativa. Basta tornar a variável acumuladora local e iterar em vez de recursar. Aqui está um exemplo em C ++ (C não fosse pelo 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, provavelmente cometi um erro no código, mas a ideia está aí.

    Mesmo usando a pilha não irá converter um algoritmo recursivo em iterativo. A recursion normal é a recursion baseada em function e, se usarmos pilha, ela se torna recursividade baseada em pilha. Mas ainda é recursivo.

    Para algoritmos recursivos, a complexidade do espaço é O (N) e a complexidade do tempo é O (N). Para algoritmos iterativos, a complexidade do espaço é O (1) e a complexidade do tempo é O (N).

    Mas se usarmos as coisas da pilha em termos de complexidade, permaneceremos iguais. Acho que apenas a recursion de cauda pode ser convertida em iteração.

    O artigo de eliminação de pilhas e recursion captura a idéia de externalizar o quadro de pilha no heap, mas não fornece uma maneira direta e repetível de converter. Abaixo está um.

    Ao converter para código iterativo, deve-se estar ciente de que a chamada recursiva pode acontecer a partir de um bloco de código arbitrariamente profundo. Não são apenas os parâmetros, mas também o ponto de retorno à lógica que resta a ser executada e o estado das variables ​​que participam das condicionais subsequentes, que são importantes. Abaixo está uma maneira muito simples de converter em código iterativo com menos alterações.

    Considere este código recursivo:

     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 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 // eg, 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 as modificações são mínimas, resultando em um menor número de erros. Para comparação, marquei as alterações com ++ e -. A maioria dos novos blocos inseridos, exceto v.push_back, é comum a qualquer lógica iterativa convertida

     void insertnode_iter(tnode *node, int num) { 

    +++++++++++++++++++++++++

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

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

     } 

    Pesquise no google por “Continuation passing style”. Existe um procedimento geral para converter em um estilo recursivo de cauda; Há também um procedimento geral para transformar funções recursivas de cauda em loops.

    Apenas matando o tempo … Uma function 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 o estouro de pilha é para funções recursivas é chamada de técnica de trampolim que é amplamente adotada pelos desenvolvedores de Java.

    No entanto, para C #, há um pequeno método auxiliar aqui que transforma sua function recursiva em iterativa sem precisar alterar a lógica ou tornar o código incompreensível. C # é uma linguagem tão legal que coisas incríveis são possíveis com isso.

    Ele funciona agrupando partes do método por um método auxiliar. Por exemplo, a seguinte function 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; } 

    Torna-se em:

     int Sum(int[] ar) { return RecursionHelper.CreateSingular(i => i >= ar.Length, i => 0) .RecursiveCall((i, rv) => i + 1) .Do((i, rv) => ar[i] + rv) .Execute(0); } 

    Um padrão para procurar é uma chamada de recursion no final da function (chamada de recursion de cauda). Isso pode ser facilmente substituído por um tempo. Por exemplo, a function 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ído 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 apenas inventei a resposta sugerindo usar uma pilha explícita que eu acho que é a solução correta e é de aplicabilidade geral.

    Quero dizer que você pode usá-lo para transformar qualquer function recursiva em uma function iterativa. Basta verificar quais valores são salvos nas chamadas recursivas, aquelas que precisam ser locais para a function recursiva e replace as chamadas por um ciclo em que você as colocará em uma pilha. Quando a pilha está vazia, a function recursiva teria sido terminada.

    Eu não posso resistir em dizer que a prova de que toda function recursiva é equivalente a uma function iterativa em um tipo de dados diferente, é uma das minhas mais queridas lembranças dos meus tempos universitários. Esse foi o curso (e o professor) que realmente me fez entender o que era a programação de computadores.

    Uma questão que havia sido fechada como uma duplicata desta tinha uma estrutura de dados muito específica:

    insira a descrição da imagem aqui

    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 function 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 invocam a si mesmas mais de uma vez (ou até mesmo uma vez). No entanto, para essa estrutura específica, isso é possível. A ideia é achatar todos os nós em uma única lista. Isso é feito colocando o 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; } } 

    Essa técnica pode ser aplicada a qualquer estrutura vinculada a dados que possa ser reduzida a um DAG com um ordenamento topológico determinístico. Os nós atuais são reorganizados para que o último filho adote todos os outros filhos. Em seguida, o nó atual pode ser excluído e o percurso pode, então, iterar para o filho restante.

    A recursion nada mais é do que o processo de chamar uma function da outra apenas esse processo é feito chamando uma function por si só. Como sabemos quando uma function chama a outra function, a primeira function salva seu estado (suas variables) e passa o controle para a function chamada. A function chamada pode ser chamada usando o mesmo nome de variables ​​ex fun1 (a) pode chamar fun2 (a). Quando fazemos chamadas recursivas, nada de novo acontece. Uma function chama a si mesma passando o mesmo tipo e similar em variables ​​de nome (mas obviamente os valores armazenados em variables ​​são diferentes, somente o nome permanece igual a). Mas antes de cada chamada, a function salva seu estado e esse processo de salvar continua. A ECONOMIA É FEITA EM UMA PILHA.

    Agora a pilha entra em jogo.

    Portanto, se você escrever um programa iterativo e salvar o estado em uma pilha a cada vez e depois extrair os valores da pilha quando necessário, terá convertido com sucesso um programa recursivo em um iterativo!

    A prova é simples e analítica.

    Na recursion, o computador mantém uma pilha e, na versão iterativa, você terá que manter manualmente a pilha.

    Pense nisso, basta converter um programa recursivo de pesquisa de primeira profundidade (em charts) em um programa iterativo de dfs.

    Muito bem sucedida!

    Pensando em coisas que realmente precisam de uma pilha:

    Se considerarmos o padrão de recursion 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 clássica Torre de Hanoi

     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 loop trabalhando em uma pilha explícita, reafirmando-a 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 a Torre de Hanói, isso se torna:

     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á considerável flexibilidade aqui em como você define sua pilha. Você pode fazer sua pilha uma lista de objects de Command que fazem coisas sofisticadas. Ou você pode ir na direção oposta e fazer uma lista de tipos mais simples (por exemplo, uma “tarefa” pode ser 4 elementos em uma pilha de int , em vez de um elemento em uma pilha de Task ).

    Tudo isso significa que a memory da pilha está no heap e não na pilha de execução do Java, mas isso pode ser útil porque você tem mais controle sobre ela.

    Uma descrição aproximada de como um sistema toma qualquer function recursiva e a executa usando uma pilha:

    Isso pretendia mostrar a ideia sem detalhes. Considere esta function que imprimiria nós de um gráfico:

     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) imprimiria B, A, C

    As chamadas de function significam salvar o estado local e o ponto de continuação para que você possa voltar e pular a function que deseja chamar.

    Por exemplo, suponha que show (A) comece a ser executado. A chamada de function na linha 3. show (B) significa – Adicione um item à pilha, significando “você precisará continuar na linha 2 com o estado da variável local node = A” – Ir para a linha 0 com o nó = B.

    Para executar o código, o sistema executa as instruções. Quando uma chamada de function é encontrada, o sistema envia informações necessárias para voltar para onde estava, executa o código de function e, quando a function é concluída, aparece a informação sobre onde ela precisa ir para continuar.

    Esse link fornece algumas explicações e propõe a idéia de manter “localização” para poder chegar ao local exato entre várias chamadas recursivas:

    No entanto, todos esses exemplos descrevem cenários nos quais uma chamada recursiva é feita em uma quantidade fixa 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 } } 

    Existe uma maneira geral de converter a passagem recursiva para o iterador usando um iterador lento que concatena vários fornecedores de iterador (expressão lambda que retorna um iterador). Veja minha Conversão Recursiva Traversal para Iterator .

    Outro exemplo simples e completo de transformar a function recursiva em iterativa usando a pilha.

     #include  #include  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 rcstack; if (b == 0) return a; rcstack.push(Par(b, a % b)); Par p; while (!rcstack.empty()) { p = rcstack.top(); rcstack.pop(); if (pb == 0) continue; rcstack.push(Par(pb, pa % pb)); } return pa; } int main() { //cout < < GCD(24, 36) << endl; cout << GCDIter(81, 36) << endl; cin.get(); return 0; }