Manera de pasar de la recursión a la iteración

349

He usado bastante la recursividad en mis muchos años de programación para resolver problemas simples, pero soy plenamente consciente de que a veces necesitas iteración debido a problemas de memoria / velocidad.

Entonces, en algún momento en el pasado, fui a tratar de encontrar si existía algún "patrón" o forma de libro de texto de transformar un enfoque de recursión común a la iteración y no encontré nada. O al menos nada que pueda recordar sería útil.

  • ¿Hay reglas generales?
  • ¿Hay un "patrón"?
Gustavo Carreño
fuente
44
Encontré esta serie informativa: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Respuestas:

334

Por lo general, reemplazo un algoritmo recursivo por un algoritmo iterativo empujando los parámetros que normalmente se pasarían a la función recursiva en una pila. De hecho, está reemplazando la pila de programas por una propia.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

Nota: si tiene más de una llamada recursiva dentro y desea preservar el orden de las llamadas, debe agregarlas en el orden inverso a la pila:

foo(first);
foo(second);

tiene que ser reemplazado por

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

Editar: El artículo Pilas y Eliminación de recursividad (o enlace de Copia de seguridad del artículo ) entra en más detalles sobre este tema.

David Segonds
fuente
44
Si reemplaza su pila con una cola, ¿eso no resuelve el problema de invertir el orden de adición?
SamuelWarren
2
Lo resolví en papel y son dos cosas diferentes. Si invierte el orden en que los agregó, lo hace avanzar hacia adelante como de costumbre, pero su recorrido sigue siendo una búsqueda profunda. Pero si cambia todo en una cola ahora está haciendo un recorrido transversal primero en lugar de primero en profundidad.
Peter
1
Recientemente hice esto de manera general, al reemplazar mi función de visita de nodo (node)->()con (node)->[actions]donde está la acción () -> [actions]. Luego, en el exterior, simplemente saca una acción / continuación de la pila, la aplica / ejecuta, empuja las acciones que devolvió en la pila en orden inverso y repite. Contingente / recorridos complejos, que acaba de capturar lo que habría sido variables de pila locales en los punteros de referencia contado que cierre otra vez en sus procesadores, entonces procesadores posteriores pueden estar supeditada a los resultados de sub-recorridos anteriores, etc.
experquisite
66
A veces evitamos la recursividad para evitar el desbordamiento de pila. Pero mantener nuestra propia pila también provocará un desbordamiento de la pila. Entonces, ¿por qué queremos implementar la recursividad con nuestra propia pila?
Zhu Li el
8
@ZhuLi Si usamos newpodemos crear un objeto en el montón en lugar de la pila. A diferencia de la pila, el montón no tiene restricciones de memoria. Ver gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

Realmente, la forma más común de hacerlo es mantener su propia pila. Aquí hay una función recursiva de clasificación rápida en 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);
}

Así es como podríamos hacerlo iterativo manteniendo nuestra propia pila:

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 ejemplo no verifica los límites de la pila ... y realmente podría dimensionar la pila en función del peor de los casos dados los valores izquierdo y derecho. Pero se entiende la idea.

bobwienholt
fuente
1
¿Alguna idea sobre cómo calcular la pila máxima para asignar para una recursión particular?
lexicalscope
@lexicalscope suponga que tiene un algoritmo recursivo O(N) = O(R*L), donde Les la suma de la complejidad "para la capa r", por ejemplo, en este caso tiene O(N)trabajo en cada paso haciendo las particiones, la profundidad recursiva es O(R), es decir, en el peor de los casos O(N), el caso promedio O(logN)aquí.
Caleth
48

Parece que nadie ha abordado dónde la función recursiva se llama a sí misma más de una vez en el cuerpo, y maneja el regreso a un punto específico en la recursión (es decir, no primitivo-recursivo). Se dice que cada recursión puede convertirse en iteración , por lo que parece que esto debería ser posible.

Se me ocurrió un ejemplo de C # de cómo hacer esto. Suponga que tiene la siguiente función recursiva, que actúa como un recorrido de postorder, y que AbcTreeNode es un árbol de 3 arios con punteros 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
        }
}

La solución 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
fuente
55
Es realmente útil, tuve que escribir una versión iterativa de reccurence que se aplica n veces, gracias a tu publicación lo hice.
Wojciech Kulik
1
Este tiene que ser el mejor ejemplo que he visto de emular la recursividad de la pila de llamadas para situaciones en las que se realizan múltiples llamadas recursivas dentro del método. Buen trabajo.
CCS
1
Usted me tuvo en "Parece que nadie ha abordado donde la función recursiva se llama a sí misma más de una vez en el cuerpo, y maneja regresar a un punto específico en la recursión" y luego ya voté. Bien, ahora voy a leer el resto de su respuesta y ver si mi voto a favor prematuro está justificado. (Porque necesito desesperadamente saber la respuesta a eso).
mydoghasworms
1
@mydoghasworms: volviendo a esta pregunta después de tanto tiempo, incluso me llevó un momento recordar lo que estaba pensando. Espero que la respuesta haya ayudado.
T. Webster
1
Me gustó la idea de esta solución, pero me pareció confusa. Escribí una versión simplificada para el árbol binario en Python, tal vez ayude a alguien a entender la idea: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
azurkin
33

Esfuércese por hacer su llamada recursiva Tail Recursion (recursividad donde la última declaración es la llamada recursiva). Una vez que tenga eso, convertirlo a iteración es generalmente bastante fácil.

Chris Shaffer
fuente
2
Algunos JIT transforman la recursión de la cola: ibm.com/developerworks/java/library/j-diag8.html
Liran Orevi
Muchos intérpretes (es decir, Scheme es el más conocido) optimizarán bien la recursividad de la cola. Sé que GCC, con una cierta optimización, hace una recursión de cola (aunque C es una elección extraña para tal optimización).
nuevo123456
19

Bueno, en general, la recursión se puede imitar como iteración simplemente usando una variable de almacenamiento. Tenga en cuenta que la recursividad y la iteración son generalmente equivalentes; uno casi siempre se puede convertir al otro. Una función recursiva de cola se convierte muy fácilmente en una iterativa. Simplemente haga que la variable del acumulador sea local e itere en lugar de recurse. Aquí hay un ejemplo en C ++ (C si no fuera por el uso de un argumento predeterminado):

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

Conociéndome, probablemente cometí un error en el código, pero la idea está ahí.

coppro
fuente
14

Incluso usar stack no convertirá un algoritmo recursivo en iterativo. La recursión normal es una recursión basada en funciones y si usamos stack se convierte en una recursión basada en stack. Pero sigue siendo una recursión.

Para algoritmos recursivos, la complejidad del espacio es O (N) y la complejidad del tiempo es O (N). Para algoritmos iterativos, la complejidad del espacio es O (1) y la complejidad del tiempo es O (N).

Pero si usamos cosas de pila en términos de complejidad, permanece igual. Creo que solo la recursión de la cola se puede convertir en iteración.

ARCO
fuente
1
Estoy de acuerdo con tu primer comentario, pero creo que no entiendo el segundo párrafo. Considere clonar una matriz simplemente copiando el copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];espacio de la memoria y la complejidad del tiempo son ambas O (N) en función del tamaño de los datos, pero es claramente un algoritmo iterativo.
Ponkadoodle
13

El artículo de eliminación de pilas y recursividad captura la idea de externalizar el marco de la pila en el montón, pero no proporciona una forma directa y repetible de convertir. Debajo hay uno.

Al convertir a código iterativo, uno debe ser consciente de que la llamada recursiva puede ocurrir desde un bloque de código arbitrariamente profundo. No son solo los parámetros, sino también el punto para volver a la lógica que queda por ejecutar y el estado de las variables que participan en condicionales posteriores, lo que importa. A continuación se muestra una forma muy simple de convertir a código iterativo con los menores cambios.

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 cómo la estructura del código sigue siendo fiel a la lógica recursiva y las modificaciones son mínimas, lo que resulta en una menor cantidad de errores. A modo de comparación, he marcado los cambios con ++ y -. La mayoría de los nuevos bloques insertados, excepto v.push_back, son comunes a cualquier 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
fuente
Esto me ha ayudado mucho, pero hay un problema: los stackitemobjetos se asignan con un valor de basura para ra. Todo sigue funcionando en el caso más parecido, pero rapor coincidencia debe ser 1 o 2, obtendrá un comportamiento incorrecto. La solución es inicializar raa 0.
JanX2
@ JanX2, stackitemno se debe presionar sin inicializar. Pero sí, inicializar a 0 detectaría errores.
Chethan
¿Por qué no se establecen ambas direcciones de retorno en la v.pop_back()declaración?
es7s
7

Busque en Google "Estilo de paso continuo". Hay un procedimiento general para convertir a un estilo recursivo de cola; También hay un procedimiento general para convertir las funciones recursivas de cola en bucles.

Marcin
fuente
6

Simplemente matando el tiempo ... Una función recursiva

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

se puede convertir a

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
fuente
El ejemplo anterior es un ejemplo de dfs recursivos a iterativos en el árbol de búsqueda binario :)
Amit
5

En general, la técnica para evitar el desbordamiento de la pila para las funciones recursivas se llama técnica de trampolín, que es ampliamente adoptada por los desarrolladores de Java.

Sin embargo, para C # hay un pequeño método auxiliar aquí que convierte su función recursiva en iterativa sin necesidad de cambiar la lógica o hacer que el código sea incomprensible. C # es un lenguaje tan agradable que es posible hacer cosas increíbles con él.

Funciona envolviendo partes del método mediante un método auxiliar. Por ejemplo, la siguiente función 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;
}

Se convierte en:

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
fuente
4

Pensando en cosas que realmente necesitan una pila:

Si consideramos el patrón de recursión 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 ejemplo, la clásica 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
}

Esto se puede traducir en un bucle que funciona en una pila explícita, reformulándolo 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 la Torre de Hanoi esto se convierte en:

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

Aquí hay una flexibilidad considerable en cuanto a cómo define su pila. Puede hacer que su pila sea una lista de Commandobjetos que hacen cosas sofisticadas. O puede ir en la dirección opuesta y hacer que sea una lista de tipos más simples (por ejemplo, una "tarea" podría ser 4 elementos en una pila de int, en lugar de un elemento en una pila de Task).

Todo esto significa que la memoria para la pila está en el montón en lugar de en la pila de ejecución de Java, pero esto puede ser útil ya que tiene más control sobre ella.

Delgado
fuente
3

Un patrón a buscar es una llamada de recursión al final de la función (llamada recursión de cola). Esto se puede reemplazar fácilmente con un tiempo. Por ejemplo, la función foo:

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

termina con un llamado a foo. Esto se puede reemplazar con:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

que elimina la segunda llamada recursiva.

Andrew Stein
fuente
3
Todavía me parece recursivo ... :)
nathan
2
Bueno, sí, pero es la mitad de recursivo. Deshacerse de la otra recursión requerirá usar otra técnica ...
Mark Bessey
2

Una pregunta que se había cerrado como duplicado de esta tenía una estructura de datos muy específica:

ingrese la descripción de la imagen aquí

El nodo tenía la siguiente estructura:

typedef struct {
    int32_t type;
    int32_t valueint;
    double  valuedouble;
    struct  cNODE *next;
    struct  cNODE *prev;
    struct  cNODE *child;
} cNODE;

La función de eliminación recursiva se veía así:

void cNODE_Delete(cNODE *c) {
    cNODE*next;
    while (c) {
        next=c->next;
        if (c->child) { 
          cNODE_Delete(c->child)
        }
        free(c);
        c=next;
    }
}

En general, no siempre es posible evitar una pila para funciones recursivas que se invocan más de una vez (o incluso una vez). Sin embargo, para esta estructura particular, es posible. La idea es aplanar todos los nodos en una sola lista. Esto se logra colocando los nodos actuales childal final de la lista de la fila 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 se puede aplicar a cualquier estructura vinculada a datos que se pueda reducir a un DAG con un orden topológico determinista. Los nodos actuales se reorganizan para que el último niño adopte a todos los otros niños. Luego, el nodo actual se puede eliminar y el recorrido puede iterar al hijo restante.

jxh
fuente
1

La recursión no es más que el proceso de llamar a una función desde la otra, solo este proceso se realiza llamando a una función por sí misma. Como sabemos cuando una función llama a la otra función, la primera función guarda su estado (sus variables) y luego pasa el control a la función llamada. La función llamada se puede llamar usando el mismo nombre de variables ex fun1 (a) puede llamar a fun2 (a). Cuando hacemos llamadas recursivas no sucede nada nuevo. Una función se llama a sí misma al pasar el mismo tipo y similares en las variables de nombre (pero obviamente los valores almacenados en las variables son diferentes, solo el nombre permanece igual). Pero antes de cada llamada, la función guarda su estado y este proceso de guardar continúa. EL AHORRO SE HACE EN UNA PILA.

AHORA LA PILA ENTRA EN JUEGO.

Entonces, si escribe un programa iterativo y guarda el estado en una pila cada vez y luego saca los valores de la pila cuando sea necesario, ¡ha convertido con éxito un programa recursivo en uno iterativo!

La prueba es simple y analítica.

En la recursividad, la computadora mantiene una pila y en la versión iterativa tendrá que mantener manualmente la pila.

Piénselo bien, simplemente convierta un programa recursivo de primera búsqueda en profundidad (en gráficos) en un programa iterativo dfs.

¡Todo lo mejor!

Ajay Manas
fuente
1

Otro ejemplo simple y completo de convertir la función recursiva en iterativa usando la pila.

#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
fuente
0

Una descripción aproximada de cómo un sistema toma cualquier función recursiva y la ejecuta usando una pila:

Esto pretendía mostrar la idea sin detalles. Considere esta función que imprimiría nodos de un 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 ejemplo, gráfico: A-> B A-> C show (A) imprimiría B, A, C

Las llamadas a funciones significan guardar el estado local y el punto de continuación para que pueda regresar y luego saltar la función que desea llamar.

Por ejemplo, suponga que show (A) comienza a ejecutarse. La llamada a la función en la línea 3. show (B) significa: Agregar elemento a la pila que significa "deberá continuar en la línea 2 con el nodo de estado variable local = A" - Ir a la línea 0 con nodo = B.

Para ejecutar el código, el sistema ejecuta las instrucciones. Cuando se encuentra una llamada a la función, el sistema envía la información que necesita para volver a donde estaba, ejecuta el código de la función y, cuando la función se completa, muestra la información sobre dónde debe ir para continuar.

Rick Giuly
fuente
0

Este enlace proporciona alguna explicación y propone la idea de mantener la "ubicación" para poder llegar al lugar exacto entre varias llamadas recursivas:

Sin embargo, todos estos ejemplos describen escenarios en los que una llamada recursiva se realiza una cantidad fija de veces. Las cosas se ponen más complicadas cuando tienes algo como:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}
Eold
fuente
0

Hay una forma general de convertir el recorrido recursivo a iterador utilizando un iterador perezoso que concatena múltiples proveedores de iteradores (expresión lambda que devuelve un iterador). Vea mi Conversión del recorrido recursivo a iterador .

Dagang
fuente
0

Mis ejemplos están en Clojure, pero deberían ser bastante fáciles de traducir a cualquier idioma.

Dada esta función que StackOverflowes para valores grandes de n:

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

podemos definir una versión que use su propia pila de la siguiente manera:

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

donde returnse define como:

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

Esto también funciona para funciones más complejas, por ejemplo, la función ackermann :

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

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

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

se puede transformar en:

(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
fuente