Sposób przejścia od rekursji do iteracji

Naprawdę, najczęstszym sposobem, aby to zrobić, jest utrzymanie własnego stosu. Oto rekurencyjna funkcja quicksort 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 jak możemy uczynić go iteratywnym, 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żna rozmiar stosu na podstawie najgorszego przypadku podane wartości lewej i prawej. Ale masz pomysł.

Wygląda na to, że nikt nie rozwiązał problemu, gdzie funkcja rekurencyjna wywołuje się więcej niż raz w ciele i obsługuje powrót do określonego punktu w rekurencji (tzn. nie jest prymitywna-rekurencyjna). Mówi się, że każda rekurencja może być zamieniona w iterację , więc wydaje się, że powinno to być możliwe.

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

Rozwiązanie iteracyjne:

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


        }

Staraj się wykonać rekurencyjne wywołanie Tail Recursion (rekurencja, gdzie ostatnie polecenie jest wywołaniem rekurencyjnym). Gdy już to masz, konwersja go do iteracji jest na ogół dość łatwa.

Ogólnie rzecz biorąc, rekurencję można naśladować jako iterację, po prostu używając zmiennej storage. Zauważ, że rekurencja i iteracja są zasadniczo równoważne; jedna może być prawie zawsze przekonwertowana na drugą. Funkcja rekurencyjna jest bardzo łatwa do przekształcenia w iteracyjną. Po prostu zmień zmienną akumulatora na lokalną i powtarzaj zamiast rekurencyjnie. 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 kod, ale pomysł jest.

Nawet użycie stosu nie przekształci algorytmu rekurencyjnego w iteracyjny. Rekurencja normalna jest rekurencją opartą na funkcji i jeśli użyjemy stosu, to staje się rekurencją opartą na stosie. Ale to wciąż rekursja.

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

Ale jeśli używamy stosu rzeczy pod względem złożoności pozostaje taka sama. Myślę, że tylko rekurencja ogonowa może być przekształcony w iterację.

Artykuł eliminacja stosów i rekursji opisuje ideę eksternalizacji ramki stosu na stercie, ale nie zapewnia prostego i powtarzalnego sposobu konwersji. Poniżej jest jeden.

Podczas konwersji na kod iteracyjny, należy mieć świadomość, że wywołanie rekurencyjne może nastąpić z arbitralnie głębokiego bloku kodu. Jego nie tylko parametry, ale także punkt powrotu do logiki, która pozostaje do wykonania i stanu zmiennych, które uczestniczyć w kolejnych uwarunkowaniach, które mają znaczenie. Poniżej znajduje się bardzo prosty sposób na konwersję do kodu iteracyjnego z najmniejszymi zmianami.

Rozważmy 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 nadal pozostaje wierna logice rekurencyjnej, a modyfikacje są minimalne, co powoduje mniejszą liczbę błędów. Dla porównania zaznaczyłem zmiany za pomocą ++ i --. Większość nowych wstawionych bloków z wyjątkiem v. push_back, są wspólne dla każda przekształcona logika iteracyjna

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

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

}

Szukaj w google " kontynuacja stylu przechodzenia."Istnieje ogólna procedura konwersji do stylu rekurencyjnego ogona; istnieje również ogólna procedura przekształcania funkcji rekurencyjnych ogona w pętle.

Zabijam czas... Funkcja rekurencyjna

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

Można przekształcić 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 technika unikania przepełnienia stosu dla funkcji rekurencyjnych nazywa się techniką trampoliny, która jest powszechnie przyjęta przez programistów Javy.

Jednak dla C# istnieje mała metoda pomocnicza tutaj, która zmienia funkcję rekurencyjną na iteracyjną bez konieczności zmiany logiki lub uczynienia kodu zrozumiałym. C# jest tak miłym językiem, że niesamowite rzeczy są możliwe dzięki niemu.

Działa poprzez zawijanie części metody za pomocą metody pomocniczej. 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;
}

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

Jednym z wzorców, których należy szukać, jest wywołanie rekurencji na końcu funkcji (tzw. rekurencja ogonowa). To można łatwo zastąpić przez 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;
     }
}

Który eliminuje drugie wywołanie rekurencyjne.

Właśnie podniosłem odpowiedź sugerującą użycie jawnego stosu, który moim zdaniem jest właściwym rozwiązaniem i ma ogólną przydatność.

Chodzi mi o to, że można go użyć do przekształcenia dowolnej funkcji rekurencyjnej w funkcję iteracyjną. Po prostu sprawdź, które wartości są zapisywane w wywołaniach rekurencyjnych, te są tymi, które mają być lokalne dla funkcji rekurencyjnej, i zastąp wywołania cyklem, w którym będziesz je przesuwać na stosie. Gdy stos jest pusty, funkcja rekurencyjna będzie zostały zlikwidowane.

Nie mogę się oprzeć, aby powiedzieć, że dowód, że każda funkcja rekurencyjna jest równoważna funkcji iteracyjnej na innym typie danych, jest jednym z moich najdroższych wspomnień z czasów uniwersyteckich. To był kurs (i profesor), który naprawdę pozwolił mi zrozumieć, na czym polega programowanie komputerowe.

A pytanie które zostało zamknięte jako DUPLIKAT tego miało 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;
    }
}

Ogólnie rzecz biorąc, nie zawsze jest możliwe uniknięcie stosu funkcji rekurencyjnych, które wywołują się więcej niż jeden raz (lub nawet raz). Jednak dla tej konkretnej struktury jest to możliwe. Chodzi o spłaszczenie wszystkich węzłów do jednej listy. Jest to możliwe dzięki umieszczeniu aktualnego węzła child na końcu listy górnego wiersza.

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

Ta technika może być zastosowana do dowolnej struktury powiązanej z danymi, którą można zredukować do DAG o deterministycznym uporządkowaniu topologicznym. Obecne dzieci węzłów są przestawiane tak, że ostatnie dziecko przyjmuje wszystkie inne dzieci. Następnie aktualny węzeł może zostać usunięty, a traversal może następnie iterację do pozostałego potomka.

Rekurencja to nic innego jak proces wywołania jednej funkcji z drugiej tylko ten proces jest wykonywany przez wywołanie funkcji samodzielnie. Jak wiemy, gdy jedna funkcja wywołuje drugą funkcję, pierwsza funkcja zapisuje swój stan(swoje zmienne), a następnie przekazuje sterowanie do wywołanej funkcji. Wywołaną funkcję można wywołać używając tej samej nazwy zmiennych np. fun1 (a) może wywołać fun2(a). Kiedy wykonujemy rekurencyjne wywołanie, nic nowego się nie dzieje. Jedna funkcja wywołuje się przekazując to samo typ i podobne w nazwach zmienne (ale oczywiście wartości zapisane w zmiennych są różne, tylko nazwa pozostaje taka sama.) do siebie. Ale przed każdym wywołaniem funkcja zapisuje swój stan i ten proces zapisywania trwa. Oszczędzanie odbywa się na stosie.

TERAZ STOS WCHODZI W GRĘ.

Więc jeśli piszesz program iteracyjny i zapisujesz stan na stosie za każdym razem, a następnie wyskakujesz wartości ze stosu w razie potrzeby, pomyślnie przekonwertowałeś program rekurencyjny na / align = "left" /

Dowód jest prosty i analityczny.

W rekurencji komputer utrzymuje stos, a w wersji iteracyjnej będziesz musiał ręcznie utrzymywać stos.

Przemyśl to, po prostu przekształć rekurencyjny program do wyszukiwania głębi (na wykresach) w program iteracyjny DFS.

Wszystkiego najlepszego!

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

Jeśli weźmiemy pod uwagę wzór 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
}

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 przetłumaczyć na pętlę pracującą na jawnym stosie, zmieniając ją 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 wieży 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 duża elastyczność w definiowaniu stosu. Możesz zrobić ze stosu listę Command obiektów, które robią wyrafinowane rzeczy. Albo ty może iść w przeciwnym kierunku i zrobić z niego listę prostszych typów(np. "zadanie" może być 4 elementami na stosie int, a nie jednym elementem na stosie Task).

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

Przybliżony opis sposobu, w jaki system przyjmuje dowolną funkcję rekurencyjną i wykonuje ją za pomocą stosu:

To miało pokazać pomysł bez szczegółów. Rozważmy tę funkcję, która wypisywałaby 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 Graf: A- > B A- > C pokaż (a) wyświetli B, A, C

Wywołania funkcji oznaczają zapisanie stanu lokalnego i punktu kontynuacji, aby można było wrócić, a następnie przeskoczyć funkcję, którą chcesz wywołać.

Na przykład, załóżmy, że show (A) zaczyna uciekaj. Wywołanie funkcji na linii 3. Pokaż (B) oznacza - Dodaj element do stosu oznaczający " musisz kontynuować w linii 2 Z local variable state node = A" - Linia Goto 0 z węzłem = B.

Aby wykonać kod, system działa zgodnie z instrukcjami. Po napotkaniu wywołania funkcji system wypycha informacje, które muszą wrócić do miejsca, w którym była, uruchamia kod funkcji, a gdy funkcja się zakończy, wyświetla informacje o tym, gdzie musi iść, aby kontynuować.

Ten link dostarcza pewnych wyjaśnień i proponuje ideę zachowania "lokalizacji", aby móc dotrzeć do dokładnego miejsca pomiędzy kilkoma wywołaniami rekurencyjnymi:

Jednak wszystkie te przykłady opisują scenariusze, w których wywołanie rekurencyjne jest wykonywane stałą ilość razy. Rzeczy stają się trudniejsze, 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 do iteratora za pomocą leniwego iteratora, który łączy wielu dostawców iteratora (wyrażenie lambda, które zwraca iterator). Zobacz mój konwertowanie rekurencyjnego przejścia na Iterator .

Kolejny prosty i kompletny przykład przekształcenia funkcji rekurencyjnej w 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;
}