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

Question

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

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

• Существуют ли общие правила?
• Есть ли "шаблон"?

Answer 1

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

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

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, но это может быть полезно, поскольку у вас больше контроля над ней.

Answer 2

Один шаблон для поиска - это рекурсивный вызов в конце функции (так называемая хвостовая рекурсия). Это может быть легко заменено на некоторое время. Например, функция 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;
     }
}

, который исключает второй рекурсивный вызов.

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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

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

Например, график: А-> Б А-> С show (A) напечатало бы B, A, C

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

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

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