Droga od rekurencji do iteracji

349

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”?
Gustavo Carreno
źródło
4
Uważam, że ta seria jest pouczająca: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Odpowiedzi:

334

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.

David Segonds
źródło
4
Jeśli zastąpisz swój stos synem kolejki, czy nie rozwiąże to problemu odwrócenia kolejności dodawania?
SamuelWarren
2
Rozpracowałem to na papierze i są to dwie różne rzeczy. Jeśli odwrócisz kolejność, w której je dodałeś, będziesz przechodził do przodu, jak zwykle, ale twoje przejście nadal jest wyszukiwaniem głębokości. Ale jeśli zmienisz wszystko w kolejkę, teraz robisz najpierw szerokość, a nie głębokość.
pete
1
Właśnie niedawno zrobił to w sposób ogólny, zastępując mój węzła funkcję odwiedzinach (node)->()z (node)->[actions]których działanie jest () -> [actions]. Następnie na zewnątrz po prostu wyskakujesz ze stosu z akcji / kontynuacji, stosujesz / wykonujesz, wypychasz akcje zwrócone na stosie w odwrotnej kolejności i powtarzasz. Przechodzenie warunkowe / złożone, po prostu przechwytujesz lokalne zmienne stosu w wskaźnikach liczonych w referencjach, które zamykasz w swoich udach, a następnie kolejne udary mogą być zależne od wyników poprzednich podróży podrzędnych itp.
znakomity
6
Czasami unikamy rekurencji, aby uniknąć przepełnienia stosu. Ale utrzymanie własnego stosu spowoduje również przepełnienie stosu. Dlaczego więc chcemy wdrożyć rekurencję z naszym własnym stosem?
Zhu Li
8
@ZhuLi Jeśli używamy new, możemy utworzyć obiekt na stercie zamiast na stosie. W przeciwieństwie do stosu, sterta nie ma ograniczeń pamięci. Zobacz gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

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ł.

Bobwienholt
źródło
1
Jakieś pomysły na to, jak obliczyć maksymalny stos do przydzielenia dla konkretnej rekurencji?
leksykalny
@lexicalscope załóżmy, że masz algorytm rekurencyjny, w O(N) = O(R*L)którym Ljest suma złożoności „dla warstwy r”, np. w tym przypadku masz O(N)pracę na każdym kroku wykonując partycjonowanie, głębokość rekurencyjna jest O(R), tj. w najgorszym przypadku O(N), średnia przypadek O(logN)tutaj.
Caleth,
48

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


        }
T. Webster
źródło
5
To naprawdę przydatne, musiałem napisać iteracyjną wersję reccurence, która nokautuje się n-razy, dzięki twojemu postowi to zrobiłem.
Wojciech Kulik
1
To musi być najlepszy przykład, jaki kiedykolwiek widziałem emulowania rekurencji stosu wywołań w sytuacjach, gdy w ramach metody wykonuje się wiele wywołań rekurencyjnych. Dobra robota.
CCS,
1
Miałeś mnie w „Wygląda na to, że nikt nie zajął się tym, gdzie funkcja rekurencyjna wywołuje się więcej niż raz w ciele i obsługuje powrót do określonego punktu w rekurencji”, a potem już głosowałem. OK, teraz przeczytam resztę twojej odpowiedzi i zobaczę, czy moje przedwczesne głosowanie było uzasadnione. (Ponieważ desperacko muszę znać odpowiedź na to pytanie).
mydoghasworms
1
@mydoghasworms - Wracając do tego pytania po tak długim czasie, zajęło mi nawet chwilę, aby przypomnieć sobie, o czym myślałem. Mam nadzieję, że odpowiedź pomogła.
T. Webster,
1
Podobało mi się pomysł tego rozwiązania, ale wydawało mi się to mylące. Napisałem uproszczoną wersję drzewa binarnego w pythonie, może pomoże komuś zrozumieć ten pomysł: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
azurkin
33

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.

Chris Shaffer
źródło
2
Niektóre rekurencyjne przekształcenia ogona JIT: ibm.com/developerworks/java/library/j-diag8.html
Liran Orevi
Mnóstwo tłumaczy (tj. Schemat jest najbardziej znany) dobrze zoptymalizuje rekurencję ogona. Wiem, że GCC, z pewną optymalizacją, wykonuje rekurencję ogona (nawet jeśli C jest dziwnym wyborem dla takiej optymalizacji).
new123456
19

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.

coppro
źródło
14

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ę.

ŁUK
źródło
1
Zgadzam się z twoją pierwszą częścią, ale myślę, że nie rozumiem drugiego akapitu. Rozważ sklonowanie tablicy po prostu przez skopiowanie copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];przestrzeni pamięci, a złożoność czasu wynosi O (N) w zależności od wielkości danych, ale jest to oczywiście algorytm iteracyjny.
Ponkadoodle
13

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

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

}
Chethan
źródło
Bardzo mi to pomogło, ale pojawia się problem: do stackitemobiektów przypisuje się wartość śmieci ra. Wszystko nadal działa w najbardziej podobnym przypadku, ale przypadkowo powinno rawynosić 1 lub 2, otrzymasz nieprawidłowe zachowanie. Rozwiązaniem jest zainicjowanie rana 0.
JanX2
@ JanX2, stackitemnie można przekazywać bez inicjowania. Ale tak, inicjowanie na 0 wychwytuje błędy.
Chethan
Dlaczego oba adresy zwrotne nie są ustawione na v.pop_back()zestawienie?
is7s
7

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.

Marcin
źródło
6

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

}
Tae-Sung Shin
źródło
Powyższy przykład jest przykładem rekurencyjnego do iteracyjnego pliku dfs w drzewie wyszukiwania binarnego :)
Amit
5

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);
}
naiem
źródło
4

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ę.

szczupły
źródło
3

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.

Andrew Stein
źródło
3
Nadal wygląda dla mnie rekurencyjnie ... :)
nathan
2
Cóż, tak - ale jest w połowie tak rekurencyjny. Pozbycie się drugiej rekurencji będzie wymagało użycia innej techniki ...
Mark Bessey,
2

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

wprowadź opis zdjęcia tutaj

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.

jxh
źródło
1

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!

Ajay Manas
źródło
1

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;
}
L_J
źródło
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ć.

Rick Giuly
źródło
0

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
  }
}
śmiały
źródło
0

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 .

Dagang
źródło
0

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)))))
divs1210
źródło