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

349

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"?
Gustavo Carreno
fonte
4
Eu encontrei esta série informativa: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Respostas:

333

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.

David Segonds
fonte
4
Se você substituir sua pilha por uma fila, isso não resolverá o problema de reverter a ordem de adição?
SamuelWarren
2
Eu trabalhei no papel e são duas coisas diferentes. Se você reverter a ordem em que os adicionou, o fará avançar como de costume, mas sua travessia ainda é a primeira pesquisa aprofundada. Mas se você mudar a coisa toda para uma fila agora, estará fazendo a primeira travessia de largura em vez de profundidade.
Pete
11
Recentemente, fiz isso de uma maneira geral, substituindo minha função de visita ao nó (node)->()por (node)->[actions]onde está a ação () -> [actions]. Então, do lado de fora, você apenas retira uma ação / continuação da pilha, aplica / executa, empurra as ações retornadas na pilha na ordem inversa e repetida. Travessias contingentes / complexas, você apenas captura o que teriam sido variáveis ​​de pilha local em ponteiros contados por referência que você fecha nos seus thunks, depois os thunks subsequentes podem depender dos resultados das sub-travessias anteriores, etc.
experiência
6
Às vezes, evitamos recursões para evitar o fluxo de pilha. Mas manter nossa própria pilha também causará um excesso de pilha. Então, por que queremos implementar recursão com nossa própria pilha?
Zhu Li
8
@ ZhuLi Se usarmos new, podemos criar um objeto na pilha em vez da pilha. Diferentemente da pilha, o heap não possui restrições de memória. Veja gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

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.

bobwienholt
fonte
11
Alguma idéia de como calcular a pilha máxima a ser alocada para uma recursão específica?
Lexicalscope 19/03/12
@lexicalscope suponha que você tenha um algoritmo recursivo O(N) = O(R*L), onde Lestá a soma da complexidade "para a camada r"; por exemplo, nesse caso, você O(N)trabalha em cada etapa da particionamento, a profundidade recursiva é O(R), ou seja, no pior caso O(N), o caso médio O(logN)aqui.
Caleth
48

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


        }
T. Webster
fonte
5
É realmente útil, eu tive que escrever uma versão iterativa de recorrência que se evoca n vezes, graças ao seu post que fiz.
Wojciech Kulik
11
Esse deve ser o melhor exemplo que eu já vi de emular a recursão da pilha de chamadas para situações em que várias chamadas recursivas estão sendo feitas dentro do método. Bom trabalho.
CCS
11
Você me disse: "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 da recursão" e então eu já votei. OK, agora vou ler o restante da sua resposta e ver se meu voto prematuro foi justificado. (Porque eu preciso desesperadamente saber a resposta para isso).
mydoghasworms
11
@mydoghasworms - Voltando a esta pergunta depois de tanto tempo, ele ainda levou -me um momento para lembrar que eu estava pensando. Espero que a resposta tenha ajudado.
T. Webster
11
Gostei da ideia desta solução, mas me pareceu confusa. Eu escrevi versão simplificada de árvore binária em python, talvez ele vai ajudar alguém a entender a idéia: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
azurkin
33

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.

Chris Shaffer
fonte
2
Alguns de JIT transformar recursão de cauda: ibm.com/developerworks/java/library/j-diag8.html
Liran Orevi
Muitos intérpretes (ou seja, o Esquema sendo o mais conhecido) otimizarão bem a recursão da cauda. Eu sei que o GCC, com uma certa otimização, faz recursão de cauda (mesmo que C seja uma escolha estranha para essa otimização).
precisa saber é o seguinte
19

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í.

coppro
fonte
14

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.

ARCO
fonte
11
Eu concordo com o seu primeiro pedaço, mas acho que estou entendendo mal o segundo parágrafo. Considere a clonagem de uma matriz através da cópia do copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];espaço da memória e da complexidade do tempo, ambos O (N) com base no tamanho dos dados, mas é claramente um algoritmo iterativo.
Ponkadoodle
13

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

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

}
Chethan
fonte
Isso me ajudou muito, mas há um problema: os stackitemobjetos são alocados com um valor de lixo para ra. Tudo ainda funciona no caso mais parecido, mas, rapor coincidência, é 1 ou 2, você terá um comportamento incorreto. A solução é inicializar raem 0.
JanX2
@ JanX2, stackitemnão deve ser pressionado sem inicializar. Mas sim, inicializar com 0 detectaria erros.
Chethan
Por que os dois endereços de retorno não estão definidos para a v.pop_back()declaração?
Is7s
7

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.

Marcin
fonte
6

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

}
Tae-Sung Shin
fonte
O exemplo acima é um exemplo de recursiva para iterativo DFS em árvore de busca binária :)
Amit
5

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);
}
naiem
fonte
4

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.

fino
fonte
3

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.

Andrew Stein
fonte
3
Ainda parece recursiva para mim ... :)
Nathan
2
Bem, sim - mas é meio recursivo. Livrar-se do outro recursão vai exigir o uso de outra técnica ...
Mark Bessey
2

Uma pergunta que foi encerrada como 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 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.

jxh
fonte
1

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!

Ajay Manas
fonte
1

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;
}
L_J
fonte
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.

Rick Giuly
fonte
0

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
  }
}
eold
fonte
0

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 .

Dagang
fonte
0

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)))))
divs1210
fonte