Путь от рекурсии к итерации

349

Я много использовал рекурсию в своих многолетних программах для решения простых задач, но я полностью осознаю, что иногда вам нужна итерация из-за проблем с памятью и скоростью.

Итак, когда-то в очень далеком прошлом я попытался найти, существует ли какой-либо «шаблон» или учебник, способ преобразования обычного рекурсивного подхода к итерации, и ничего не нашел. Или, по крайней мере, ничего, что я помню, это не помогло бы.

  • Есть ли общие правила?
  • Есть ли «шаблон»?
Густаво Каррено
источник
4
Я нашел эту серию информативной: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Ответы:

334

Обычно я заменяю рекурсивный алгоритм итеративным алгоритмом, помещая параметры, которые обычно передаются рекурсивной функции в стек. Фактически, вы заменяете программный стек одним своим.

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

  // Push other objects on the stack.

}

Примечание: если у вас более одного рекурсивного вызова внутри и вы хотите сохранить порядок вызовов, вы должны добавить их в обратном порядке в стек:

foo(first);
foo(second);

должен быть заменен

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

Изменить: статья Стеки и устранение рекурсии (или ссылка Резервное копирование статьи ) входит в более подробную информацию по этому вопросу.

Дэвид Сегондс
источник
4
Если вы замените свой стек очередью, разве это не решит проблему изменения порядка добавления?
Сэмюэль Уоррен
2
Я разработал это на бумаге, и это две разные вещи. Если вы измените порядок, в котором вы их добавили, это заставит вас двигаться вперед, как обычно, но ваш поиск все еще является поиском в глубину. Но если вы превратили все это в очередь, то теперь вы делаете обход в ширину, а не в глубину.
Пит
1
Я только недавно сделал это в общем виде, путем замены моего узла функцию посмотреть недвижимость (node)->()с , (node)->[actions]где действие () -> [actions]. Затем снаружи вы просто выталкиваете действие / продолжение из стека, применяете / выполняете его, перемещаете действия, которые оно вернуло в стек, в обратном порядке и повторяете. Случайные / сложные обходы, вы просто фиксируете то, что было бы локальными переменными стека в указателях с подсчетом ссылок, которые вы закрываете в своих группах, тогда последующие
блоки группировок
6
Иногда мы избегаем рекурсии, чтобы избежать переполнения стека. Но поддержание нашего собственного стека также вызовет переполнение стека. Итак, почему мы хотим реализовать рекурсию с нашим собственным стеком?
Чжу Ли
8
@ZhuLi Если мы используем, newмы можем создать объект в куче, а не в стеке. В отличие от стека, куча не имеет ограничений памяти. См. Gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

Действительно, самый распространенный способ сделать это - сохранить свой собственный стек. Вот рекурсивная функция быстрой сортировки в 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);
}

Вот как мы могли бы сделать его итеративным, сохранив свой собственный стек:

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

Очевидно, что этот пример не проверяет границы стека ... и на самом деле вы можете определить размер стека на основе наихудшего случая с учетом левого и правого значений. Но Вы получаете идею.

bobwienholt
источник
1
Любые идеи о том, как определить максимальный стек для конкретной рекурсии?
лексический обзор
@lexicalscope предположим, что у вас есть рекурсивный алгоритм O(N) = O(R*L), где Lесть сумма сложности "для слоя r", например, в этом случае у вас есть O(N)работа на каждом шаге, делающем разбиения, рекурсивная глубина O(R), то есть наихудший случай O(N), является средним случаем O(logN)здесь.
Caleth
48

Кажется, никто не обращался к тому, где рекурсивная функция вызывает себя более одного раза в теле и обрабатывает возврат к определенной точке рекурсии (то есть не является примитивно-рекурсивной). Говорят, что каждая рекурсия может быть превращена в итерацию , поэтому кажется, что это должно быть возможно.

Я только что придумал пример C #, как это сделать. Предположим, у вас есть следующая рекурсивная функция, которая действует как обход по порядку и что AbcTreeNode - это 3-арное дерево с указателями 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
        }
}

Итеративное решение:

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


        }
Т. Вебстер
источник
5
Это действительно полезно, мне пришлось написать итеративную версию восстановления, которая запускается n раз, благодаря вашему посту, я сделал это.
Войцех Кулик
1
Это должен быть лучший пример, который я когда-либо видел в эмуляции рекурсии стека вызовов для ситуаций, когда в методе выполняется несколько рекурсивных вызовов. Хорошая работа.
CCS
1
Я сказал вам: «Кажется, никто не обращался, когда рекурсивная функция вызывает себя в теле более одного раза и обрабатывает возврат к определенной точке рекурсии», и тогда я уже проголосовал. Хорошо, теперь я собираюсь прочитать остальную часть вашего ответа и посмотреть, был ли мой преждевременный ответ оправданным. (Потому что мне отчаянно нужно знать ответ на этот вопрос).
mydoghasworms
1
@mydoghasworms - Возвращаясь к этому вопросу после того, как так долго, он даже взял меня на мгновение , чтобы вспомнить , что я думал. Надеюсь, что ответ помог.
Т. Вебстер
1
Мне понравилась идея этого решения, но оно показалось мне запутанным. Я написал упрощенную версию для двоичного дерева на python, возможно, это поможет кому-то понять идею: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
azurkin
33

Стремитесь сделать рекурсивный вызов Tail Recursion (рекурсия, где последним оператором является рекурсивный вызов). Если у вас есть это, преобразовать его в итерацию, как правило, довольно легко.

Крис Шаффер
источник
2
Некоторая JIT-трансформационная хвостовая рекурсия: ibm.com/developerworks/java/library/j-diag8.html
Лиран Ореви
Множество интерпретаторов (т. Е. Наиболее известная схема) хорошо оптимизируют хвостовую рекурсию. Я знаю, что GCC с определенной оптимизацией выполняет хвостовую рекурсию (даже если C является странным выбором для такой оптимизации).
new123456
19

Ну, в общем, рекурсию можно имитировать как итерацию, просто используя переменную хранения. Обратите внимание, что рекурсия и итерация обычно эквивалентны; одно почти всегда может быть преобразовано в другое. Хвосто-рекурсивная функция очень легко преобразуется в итеративную. Просто сделайте переменную аккумулятора локальной, и выполняйте итерацию вместо recurse. Вот пример на C ++ (если бы не использование аргумента по умолчанию):

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

Зная меня, я, вероятно, допустил ошибку в коде, но идея есть.

coppro
источник
14

Даже использование стека не преобразует рекурсивный алгоритм в итеративный. Обычная рекурсия - это рекурсия, основанная на функциях, и если мы используем стек, то она становится рекурсией, основанной на стеке. Но это все еще рекурсия.

Для рекурсивных алгоритмов сложность пространства равна O (N), а сложность времени - O (N). Для итерационных алгоритмов сложность пространства равна O (1), а сложность времени равна O (N).

Но если мы используем стек вещей с точки зрения сложности остается тем же. Я думаю, что только хвостовая рекурсия может быть преобразована в итерацию.

ARC
источник
1
Я согласен с вашей первой частью, но мне кажется, что я неправильно понимаю второй абзац. Рассмотрим клонирование массива путем простого копирования copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];пространства памяти, а сложность времени - O (N) в зависимости от размера данных, но это явно итерационный алгоритм.
Ponkadoodle
13

В статье, посвященной удалению стеков и рекурсии, отражена идея экстернализации кадра стека в куче, но не предоставляется простой и воспроизводимый способ преобразования. Ниже один.

При преобразовании в итеративный код необходимо учитывать, что рекурсивный вызов может происходить из произвольно глубокого блока кода. Это не только параметры, но и точка возврата к логике, которую еще предстоит выполнить, и состояние переменных, которые участвуют в последующих условных выражениях, которые имеют значение. Ниже приведен очень простой способ преобразования в итеративный код с наименьшими изменениями.

Рассмотрим этот рекурсивный код:

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

Итерационный код:

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

Обратите внимание, что структура кода все еще остается верной рекурсивной логике, а модификации минимальны, что приводит к меньшему количеству ошибок. Для сравнения я пометил изменения с ++ и -. Большинство новых вставленных блоков, кроме v.push_back, являются общими для любой преобразованной итерационной логики.

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
источник
Это мне очень помогло, но есть проблема: stackitemобъекты выделяются со значением мусора для ra. Все по-прежнему работает в наиболее похожем случае, но если raпо совпадению будет 1 или 2, вы получите неправильное поведение. Решение состоит в том, чтобы инициализировать raдо 0.
JanX2
@ JanX2, stackitemнельзя нажимать без инициализации. Но да, инициализация в 0 будет ловить ошибки.
Четан
Почему v.pop_back()вместо обоих адресов возврата не указано выражение?
is7s
7

Поиском в Google "Стиль продолжения продолжения". Существует общая процедура для преобразования в хвостовой рекурсивный стиль; Существует также общая процедура преобразования хвостовых рекурсивных функций в циклы.

Marcin
источник
6

Просто убивает время ... Рекурсивная функция

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

может быть преобразован в

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

}
Тае Сунг Шин
источник
Приведенный выше пример является примером рекурсивного итеративного dfs в бинарном дереве поиска :)
Amit
5

Обычно метод, позволяющий избежать переполнения стека для рекурсивных функций, называется методом батута, который широко применяется разработчиками Java.

Однако, для C # есть небольшой вспомогательный метод здесь , что превращает вашу рекурсивную функцию итерационного , не требуя к логике изменения или сделать код-понятным. C # - такой приятный язык, что с ним можно создавать удивительные вещи.

Он работает, оборачивая части метода вспомогательным методом. Например, следующая рекурсивная функция:

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

Превращается в:

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
источник
4

Думая о вещах, которые действительно нуждаются в стеке:

Если мы рассмотрим шаблон рекурсии как:

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
}

Например, классическая Ханойская башня

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
}

Это может быть преобразовано в цикл, работающий с явным стеком, путем его преобразования:

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

Для Ханойской Башни это становится:

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

Здесь есть большая гибкость в отношении того, как вы определяете свой стек. Вы можете сделать свой стек списком Commandобъектов, которые делают сложные вещи. Или вы можете пойти в противоположном направлении и составить список простых типов (например, «задание» может быть 4 элемента в стеке int, а не один элемент в стеке Task).

Все это означает, что память для стека находится в куче, а не в стеке выполнения Java, но это может быть полезно, поскольку у вас больше контроля над ней.

тонкий
источник
3

Один шаблон для поиска - это рекурсивный вызов в конце функции (так называемая хвостовая рекурсия). Это может быть легко заменено на некоторое время. Например, функция foo:

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

заканчивается звонком в foo. Это можно заменить на:

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

который устраняет второй рекурсивный вызов.

Эндрю Стейн
источник
3
Все еще выглядит рекурсивно для меня ... :)
Натан
2
Ну да - но это наполовину рекурсивно. Чтобы избавиться от другой рекурсии, потребуется использовать другую технику ...
Марк Бесси
2

Вопрос , который был закрыт как дубликат этой имел очень специфическую структуру данных:

введите описание изображения здесь

Узел имел следующую структуру:

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

Функция рекурсивного удаления выглядела так:

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

В общем, не всегда возможно избежать стека для рекурсивных функций, которые вызывают себя более одного раза (или даже один раз). Однако для этой конкретной структуры это возможно. Идея состоит в том, чтобы объединить все узлы в один список. Это достигается путем помещения текущего узла childв конец списка верхней строки.

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

Этот метод может быть применен к любой связанной с данными структуре, которая может быть преобразована в группу доступности базы данных с детерминированным топологическим порядком. Текущие дочерние узлы переставляются так, что последний дочерний элемент принимает всех остальных дочерних элементов. Затем текущий узел может быть удален, и обход может затем перейти к оставшемуся дочернему элементу.

jxh
источник
1

Рекурсия - это не что иное, как процесс вызова одной функции из другой, только этот процесс выполняется путем вызова самой функции. Как мы знаем, когда одна функция вызывает другую функцию, первая функция сохраняет свое состояние (свои переменные), а затем передает управление вызываемой функции. Вызываемая функция может быть вызвана с использованием одного и того же имени переменных. Ex fun1 (a) может вызвать fun2 (a). Когда мы делаем рекурсивный вызов, ничего нового не происходит. Одна функция вызывает себя, передавая один и тот же тип и похожие по имени переменные (но, очевидно, значения, хранящиеся в переменных, различаются, только имя остается тем же самым). Но перед каждым вызовом функция сохраняет свое состояние, и этот процесс сохранения продолжается. ЭКОНОМИЯ СДЕЛАНА НА СТЕКЕ.

СЕЙЧАС СТЕК ВХОДИТ В ИГРА.

Поэтому, если вы пишете итеративную программу и каждый раз сохраняете состояние в стеке, а затем извлекаете значения из стека, когда это необходимо, вы успешно преобразовали рекурсивную программу в итеративную!

Доказательство простое и аналитическое.

В рекурсии компьютер поддерживает стек, а в итерационной версии вам придется вручную поддерживать стек.

Подумайте об этом, просто преобразуйте рекурсивную программу поиска в глубину (на графиках) в итерационную программу dfs.

Всего наилучшего!

Аджай Манас
источник
1

Еще один простой и полный пример превращения рекурсивной функции в итеративную с использованием стека.

#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
источник
0

Грубое описание того, как система берет любую рекурсивную функцию и выполняет ее, используя стек:

Это призвано показать идею без подробностей. Рассмотрим эту функцию, которая распечатывает узлы графа:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

Например, график: A-> B A-> C show (A) выведет B, A, C

Вызов функции означает сохранение локального состояния и точки продолжения, чтобы вы могли вернуться и затем перейти к функции, которую вы хотите вызвать.

Например, предположим, что шоу (A) начинает работать. Вызов функции в строке 3. show (B) означает - Добавить элемент в стек, что означает «вам нужно продолжить со строки 2 с локальной переменной state node = A» - Перейти к строке 0 с node = B.

Чтобы выполнить код, система выполняет инструкции. Когда происходит вызов функции, система отправляет информацию, необходимую для возврата туда, где она была, запускает код функции, а когда функция завершается, выдает информацию о том, куда ей нужно перейти, чтобы продолжить.

Рик Джули
источник
0

Эта ссылка дает некоторое объяснение и предлагает идею сохранения «местоположения», чтобы иметь возможность добраться до точного места между несколькими рекурсивными вызовами:

Однако все эти примеры описывают сценарии, в которых рекурсивный вызов выполняется фиксированное количество раз. Все становится сложнее, когда у вас есть что-то вроде:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}
eold
источник
0

Существует общий способ преобразования рекурсивного обхода в итератор с помощью ленивого итератора, который объединяет нескольких поставщиков итераторов (лямбда-выражение, которое возвращает итератор). Смотрите мой Преобразование рекурсивного обхода в итератор .

Даган
источник
0

Мои примеры в Clojure, но их должно быть довольно легко перевести на любой язык.

Учитывая эту функцию, которая StackOverflows для больших значений n:

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

мы можем определить версию, которая использует свой собственный стек следующим образом:

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

где returnопределяется как:

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

Это работает и для более сложных функций, например, функции ackermann :

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

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

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

может быть преобразован в:

(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
источник