Droga od rekurencji do iteracji

Użyłem rekurencji podczas wielu lat programowania, aby rozwiązać proste problemy, ale jestem w pełni świadomy, że czasami potrzebujesz iteracji z powodu problemów z pamięcią / prędkością.

Kiedyś więc w bardzo odległej przeszłości szukałem, czy istnieje jakiś „wzorzec” lub podręcznikowy sposób przekształcania wspólnego podejścia do iteracji i nie znalazłem niczego. A przynajmniej nic, co pamiętam, nie pomogłoby.

• Czy istnieją ogólne zasady?
• Czy istnieje „wzór”?

Zwykle zastępuję algorytm rekurencyjny algorytmem iteracyjnym, wypychając parametry, które normalnie byłyby przekazywane do funkcji rekurencyjnej na stos. W rzeczywistości zastępujesz stos programów jednym z własnych.

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

  // Push other objects on the stack.

}

Uwaga: jeśli masz w środku więcej niż jedno wywołanie rekurencyjne i chcesz zachować kolejność wywołań, musisz dodać je do stosu w odwrotnej kolejności:

foo(first);
foo(second);

musi zostać zastąpiony przez

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

Edycja: Artykuł Eliminacja stosów i rekurencji (lub link Tworzenie kopii zapasowej artykułu ) zawiera więcej szczegółów na ten temat.

Naprawdę najczęstszym sposobem na to jest utrzymanie własnego stosu. Oto rekurencyjna funkcja szybkiego sortowania w 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);
}

Oto, w jaki sposób możemy iterować, utrzymując własny stos:

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

Oczywiście, ten przykład nie sprawdza granic stosu ... i naprawdę możesz określić rozmiar stosu w oparciu o najgorszy przypadek, podając lewą i prawą wartość. Ale masz pomysł.

Wydaje się, że nikt nie zajął się tym, gdzie funkcja rekurencyjna wywołuje się w ciele więcej niż jeden raz w ciele i obsługuje powrót do określonego punktu rekurencji (tj. Nie prymitywno-rekurencyjny). Mówi się, że każdą rekurencję można przekształcić w iterację , więc wydaje się, że powinno to być możliwe.

Właśnie wymyśliłem przykład C # jak to zrobić. Załóżmy, że masz następującą funkcję rekurencyjną, która działa jak przechodzenie w postorder, a AbcTreeNode jest 3-arytowym drzewem ze wskaźnikami 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
        }
}

Iteracyjne rozwiązanie:

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


        }

Postaraj się wykonać połączenie rekurencyjne Tail Recursion (rekursja, w której ostatnim wyrażeniem jest połączenie rekurencyjne). Gdy już to zrobisz, konwersja na iterację jest ogólnie dość łatwa.

Zasadniczo rekurencję można naśladować jako iterację, używając po prostu zmiennej pamięci. Zauważ, że rekurencja i iteracja są na ogół równoważne; jedno można prawie zawsze przekonwertować na drugie. Funkcję rekurencyjną ogona można bardzo łatwo przekształcić w funkcję iteracyjną. Po prostu ustaw zmienną akumulatorową na lokalną i iteruj zamiast powtarzać. Oto przykład w C ++ (C gdyby nie użycie domyślnego argumentu):

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

Znając mnie, prawdopodobnie popełniłem błąd w kodzie, ale pomysł już istnieje.

Nawet użycie stosu nie przekształci algorytmu rekurencyjnego w iteracyjny. Normalna rekurencja jest rekurencją zależną od funkcji i jeśli użyjemy stosu, stanie się rekurencją stosową. Ale to wciąż rekurencja.

W przypadku algorytmów rekurencyjnych złożoność przestrzeni wynosi O (N), a złożoność czasu wynosi O (N). W przypadku algorytmów iteracyjnych złożoność przestrzeni wynosi O (1), a złożoność czasu wynosi O (N).

Ale jeśli używamy stosu, rzeczy pod względem złożoności pozostają takie same. Myślę, że tylko rekurencję ogona można przekształcić w iterację.

Te stosy i eliminacja rekursji przechwytuje artykuł idea uzewnętrzniania ramkę stosu na kupie, ale nie zapewnia proste i powtarzalne sposób przekonwertować. Poniżej jest jeden.

Podczas konwertowania na kod iteracyjny należy pamiętać, że wywołanie rekurencyjne może nastąpić z dowolnego głęboko kodu bloku. Liczy się nie tylko parametry, ale także punkt powrotu do logiki, która pozostaje do wykonania, i stanu zmiennych, które uczestniczą w kolejnych warunkach, które mają znaczenie. Poniżej znajduje się bardzo prosty sposób na konwersję do kodu iteracyjnego z najmniejszymi zmianami.

Rozważ ten kod rekurencyjny:

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

Kod iteracyjny:

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

Zauważ, że struktura kodu wciąż pozostaje zgodna z logiką rekurencyjną, a modyfikacje są minimalne, co powoduje mniej błędów. Dla porównania zaznaczyłem zmiany ++ i -. Większość nowych wstawionych bloków oprócz v.push_back jest wspólna dla każdej przekonwertowanej logiki iteracyjnej

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

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

}

Wyszukaj w Google hasło „Styl przekazywania kontynuacji”. Istnieje ogólna procedura konwersji na styl rekurencyjny ogona; istnieje również ogólna procedura przekształcania funkcji rekurencyjnych w ogony w pętle.

Tylko zabijanie czasu ... Funkcja rekurencyjna

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

można przekonwertować na

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

}

Ogólnie rzecz biorąc, technika unikania przepełnienia stosu dla funkcji rekurencyjnych nazywa się techniką trampoliny, która jest powszechnie stosowana przez programistów Java.

Jednak w języku C # istnieje tutaj niewielka metoda pomocnicza , która zmienia funkcję rekurencyjną w iteracyjną bez konieczności zmiany logiki lub uczynienia kodu niezrozumiałym. C # jest tak fajnym językiem, że możliwe są przy nim niesamowite rzeczy.

Działa poprzez owijanie części metody metodą pomocniczą. Na przykład następująca funkcja rekurencyjna:

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

Przemienia się w:

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

Myślenie o rzeczach, które faktycznie potrzebują stosu:

Jeśli weźmiemy pod uwagę wzorzec rekurencji jako:

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
}

Na przykład klasyczna wieża w 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
}

Można to przełożyć na pętlę działającą na jawnym stosie, przekształcając go jako:

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

Dla Tower of Hanoi staje się to:

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

Istnieje znaczna elastyczność w definiowaniu stosu. Możesz ustawić swój stos jako listęCommand obiektów wykonujących skomplikowane czynności. Lub możesz pójść w przeciwnym kierunku i uczynić go listą prostszych typów (np. „Zadaniem” mogą być 4 elementy na stosie int, a nie jeden element na stosie Task).

Wszystko to oznacza, że ​​pamięć stosu znajduje się w stercie, a nie w stosie wykonawczym Java, ale może to być przydatne, ponieważ masz nad nią większą kontrolę.

Jednym z wzorców, których należy szukać, jest wywołanie rekurencyjne na końcu funkcji (tzw. Rekurencja ogona). Można to łatwo zastąpić chwilą. Na przykład funkcja foo:

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

kończy się wezwaniem do foo. Można to zastąpić:

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

co eliminuje drugie wywołanie rekurencyjne.

Pytanie , który został zamknięty jako duplikat ten miał bardzo specyficzną strukturę danych:

Węzeł miał następującą strukturę:

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

Funkcja usuwania rekurencyjnego wyglądała następująco:

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

Zasadniczo nie zawsze można uniknąć stosu funkcji rekurencyjnych, które wywołują się więcej niż jeden raz (lub nawet raz). Jednak w przypadku tej konkretnej struktury jest to możliwe. Chodzi o spłaszczenie wszystkich węzłów w jedną listę. Dokonuje się tego poprzez umieszczenie bieżącego węzła childna końcu listy górnego rzędu.

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

Technikę tę można zastosować do dowolnej struktury powiązanej z danymi, którą można zredukować do DAG z deterministycznym uporządkowaniem topologicznym. Obecne dzieci węzłów są przestawiane w taki sposób, aby ostatnie dziecko adoptowało wszystkie pozostałe dzieci. Następnie bieżący węzeł można usunąć, a przejście może następnie wykonać iterację z pozostałym dzieckiem.

Rekurencja jest niczym innym jak procesem wywoływania jednej funkcji od drugiej, tylko ten proces odbywa się przez wywołanie funkcji samodzielnie. Jak wiemy, gdy jedna funkcja wywołuje drugą funkcję, pierwsza funkcja zapisuje swój stan (jej zmienne), a następnie przekazuje sterowanie do wywoływanej funkcji. Wywołaną funkcję można wywołać, używając tej samej nazwy zmiennych ex fun1 (a) może wywołać fun2 (a). Kiedy wykonujemy połączenie rekurencyjne, nic nowego się nie dzieje. Jedna funkcja wywołuje się, przekazując do siebie ten sam typ i podobne zmienne nazw (ale oczywiście wartości przechowywane w zmiennych są różne, tylko nazwa pozostaje taka sama). Ale przed każdym wywołaniem funkcja zapisuje swój stan i proces zapisywania trwa. OSZCZĘDNOŚĆ JEST WYKONYWANA NA stosie.

TERAZ STOSUJE SIĘ DO GRY.

Więc jeśli napiszesz program iteracyjny i za każdym razem zapiszesz stan na stosie, a następnie wyodrębnisz wartości ze stosu w razie potrzeby, pomyślnie przekształciłeś program rekurencyjny w program iteracyjny!

Dowód jest prosty i analityczny.

W rekursji komputer utrzymuje stos, aw wersji iteracyjnej będziesz musiał ręcznie utrzymywać stos.

Zastanów się, po prostu przekonwertuj program rekursywny pierwszego wyszukiwania głębokości (na wykresach) na iteracyjny program dfs.

Wszystkiego najlepszego!

Kolejny prosty i kompletny przykład zamiany funkcji rekurencyjnej na iteracyjną przy użyciu stosu.

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

Zwięzły opis tego, jak system przyjmuje jakąkolwiek funkcję rekurencyjną i wykonuje ją za pomocą stosu:

Miało to pokazać pomysł bez szczegółów. Rozważ tę funkcję, która wypisuje węzły wykresu:

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

Na przykład wykres: A-> B A-> C pokaż (A) wydrukuje B, A, C.

Wywołania funkcji oznaczają zapisanie stanu lokalnego i punktu kontynuacji, abyś mógł wrócić, a następnie przeskoczyć funkcję, którą chcesz wywołać.

Załóżmy na przykład, że show (A) zaczyna działać. Wywołanie funkcji w linii 3. pokaż (B) oznacza - Dodaj element do stosu, co oznacza, że ​​„musisz kontynuować w linii 2 z lokalnym stanem zmiennej węzeł = A” - Przejdź do linii 0 z węzłem = B.

Aby wykonać kod, system wykonuje instrukcje. Po napotkaniu wywołania funkcji system wypycha informacje, które muszą wrócić do miejsca, w którym się znajdował, uruchamia kod funkcji, a po zakończeniu funkcji wyświetla informacje o tym, dokąd musi przejść, aby kontynuować.

Ten link zawiera pewne wyjaśnienia i proponuje zachowanie „lokalizacji”, aby móc dotrzeć do dokładnego miejsca między kilkoma wywołaniami rekurencyjnymi:

Jednak wszystkie te przykłady opisują scenariusze, w których wywołanie rekurencyjne jest wykonywane określoną liczbę razy. Sprawa staje się trudniejsza, gdy masz coś takiego:

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

Istnieje ogólny sposób konwersji rekurencyjnego przejścia na iterator za pomocą leniwego iteratora, który łączy wielu dostawców iteratorów (wyrażenie lambda, które zwraca iterator). Zobacz moje przekształcanie rekurencyjnego przejścia do iteratora .

Moje przykłady są w Clojure, ale powinny być dość łatwe do przetłumaczenia na dowolny język.

Biorąc pod uwagę tę funkcję, która StackOverflowdotyczy dużych wartości n:

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

możemy zdefiniować wersję, która używa własnego stosu w następujący sposób:

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

gdzie returnjest zdefiniowany jako:

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

Działa to również w przypadku bardziej złożonych funkcji, na przykład funkcji ackermann :

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

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

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

można przekształcić w:

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