Caminho a percorrer da recursão para a iteração

Eu usei bastante a recursão nos meus muitos anos de programação para resolver problemas simples, mas tenho plena consciência de que às vezes você precisa de iteração devido a problemas de memória / velocidade.

Então, em algum momento no passado, tentei descobrir se havia alguma maneira "padrão" ou de livro didático de transformar uma abordagem de recursão comum à iteração e não encontrei nada. Ou pelo menos nada do que me lembre ajudaria.

• Existem regras gerais?
• Existe um "padrão"?

Normalmente, substituo um algoritmo recursivo por um algoritmo iterativo, pressionando os parâmetros que normalmente seriam passados ​​para a função recursiva em uma pilha. Na verdade, você está substituindo a pilha de programas por uma de sua preferência.

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 e deseja preservar a ordem das chamadas, adicione-as na ordem inversa à pilha:

foo(first);
foo(second);

deve ser substituído por

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

Edit: O artigo Eliminação de pilhas e recursões (ou link de backup do artigo ) entra em mais detalhes sobre este assunto.

Realmente, a maneira mais comum de fazer isso é manter sua própria pilha. Aqui está uma função 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 os limites da pilha ... e realmente você pode dimensionar a pilha com base no pior caso, com os valores esquerdo e direito. Mas você entendeu.

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

Eu apenas vim com um exemplo de C # de como fazer isso. Suponha que você tenha a seguinte função recursiva, que age como uma passagem pós-ordem, e que AbcTreeNode é uma árvore de 3 árias 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 sua chamada recursiva Tail Recursion (recursão em que a última instrução é a chamada recursiva). Depois disso, a conversão para iteração geralmente é bastante fácil.

Bem, em geral, a recursão pode ser imitada como iteração simplesmente usando uma variável de armazenamento. Observe que recursão e iteração são geralmente equivalentes; um quase sempre pode ser convertido no outro. Uma função recursiva da cauda é facilmente convertida em uma iterativa. Apenas torne a variável acumuladora local e itere 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 converterá um algoritmo recursivo em iterativo. Recursão normal é recursão baseada em função e, se usarmos pilha, ela se tornará recursão baseada em pilha. Mas ainda é recursão.

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 as mesmas. Eu acho que apenas a recursão da cauda pode ser convertida em iteração.

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

Ao converter para código iterativo, é preciso estar ciente de que a chamada recursiva pode ocorrer a partir de um bloco de código arbitrariamente profundo. Não são apenas os parâmetros, mas também o ponto de retornar à lógica que resta a ser executada e ao estado das variáveis ​​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<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 as modificações são mínimas, resultando em menor número de bugs. 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<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();
    }

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

}

Pesquise no google por "Estilo de passagem contínua". Existe um procedimento geral para converter para um estilo recursivo de cauda; também existe um procedimento geral para transformar funções recursivas da cauda em loops.

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 o estouro de pilha é para funções recursivas, chamada técnica de trampolim, amplamente adotada pelos desenvolvedores Java.

No entanto, para C #, existe um pequeno método auxiliar 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 agradável que coisas incríveis são possíveis com ela.

Ele funciona agrupando 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;
}

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

Pensando em coisas que realmente precisam 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 clássica torre 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 loop que trabalha em uma pilha explícita, atualizando-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 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()));
    }
}

Aqui há uma flexibilidade considerável sobre como você define sua pilha. Você pode fazer da sua pilha uma lista de Commandobjetos 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 de 4 elementos em uma pilha de int, em vez de um elemento em uma pilha de Task).

Tudo isso significa que a memória da pilha está na pilha e não na pilha de execução Java, mas isso pode ser útil, pois você tem mais controle sobre ela.

Um padrão a ser procurado é uma chamada de recursão no final da função (chamada recursão de cauda). 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í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.

Uma pergunta que foi encerrada como duplicata desta tinha uma estrutura de dados muito específica:

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 com:

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 chamam mais de uma vez (ou mesmo uma vez). No entanto, para essa estrutura específica, é possível. A idéia é achatar todos os nós em uma única lista. Isso é feito colocando os nós atuais childno 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 uma ordem topológica determinística. Os nós dos filhos atuais são reorganizados para que o último filho adote todos os outros filhos. Em seguida, o nó atual pode ser excluído e a travessia pode iterar para o filho restante.

A recursão nada mais é do que o processo de chamar uma função da outra, somente esse processo é feito chamando uma função por si só. Como sabemos quando uma função chama a outra, a primeira função salva seu estado (suas variáveis) e passa o controle para a função chamada. A função chamada pode ser chamada usando o mesmo nome de variáveis ​​ex fun1 (a) pode chamar fun2 (a). Quando fazemos chamadas recursivas, nada de novo acontece. Uma função chama a si mesma passando o mesmo tipo e similar nas variáveis ​​de nome (mas, obviamente, os valores armazenados nas variáveis ​​são diferentes, apenas o nome permanece o mesmo.) Para si mesmo. Porém, antes de cada chamada, a função salva seu estado e esse processo de economia continua. A ECONOMIA É FEITO EM UMA PILHA.

Agora a pilha entra em jogo.

Portanto, se você escrever um programa iterativo e salvar o estado em uma pilha de cada vez e depois exibir os valores da pilha quando necessário, você converteu com êxito um programa recursivo em um iterativo!

A prova é simples e analítica.

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

Pense bem, basta converter um programa recursivo de pesquisa em profundidade (em gráficos) em um programa iterativo dfs.

Muito bem sucedida!

Outro exemplo simples e completo de transformar a função recursiva em iterativa 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;
}

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

Isso pretendia mostrar a ideia sem detalhes. Considere esta função 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 mostra (A) imprimiria B, A, C

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

Por exemplo, suponha que o show (A) comece a ser executado. A chamada de função na linha 3. show (B) significa - Adicione um item à pilha, significando "você precisará continuar na linha 2 com o estado variável local node = A" - Vá para a linha 0 com o nó = B.

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

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

No entanto, todos esses exemplos descrevem cenários em que uma chamada recursiva é feita 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 em iterador usando um iterador lento que concatena vários fornecedores de iteradores (expressão lambda que retorna um iterador). Veja meu Convertendo Recursivo Traversal para Iterator .

Meus exemplos estão no Clojure, mas deve ser bastante fácil de traduzir para qualquer idioma.

Dada esta função que StackOverflowé para grandes valores de n:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

podemos definir uma versão que usa sua própria pilha da seguinte maneira:

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

onde returné definido como:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

Isso também funciona para funções mais complexas, por exemplo, a função ackermann :

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

pode ser transformado em:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))