Zapisywanie algorytmów rekurencyjnych w sposób iteracyjny Mariusz: Zapisywanie algorytmów rekurencyjnych w sposób iteracyjny Pytający gdybyś miał poprowadzić lekcję na ten temat to co by ona zawierała ? Co do przykładów Cormen i reszta zapisali procedurę przywracającą kopiec w sposób rekurencyjny Procedura sortująca przez scalanie jest przedstawiana zwykle rekurencyjnie chociaż spotkałem się też z tym że procedura scalająca także była zapisana rekurencyjnie Procedura sortowania przez podział (może zwolnić do n² więc nie jest wcale takie szybkie) także jest zapisywana rekurencyjnie Wyszukiwania zarówno liniowe jak i binarne też mogą być zapisane rekurencyjnie Co do procedury przywracającej kopiec to Trivial zastąpił rekurencję skokiem

Pytający: Hmmm, na pewno rekurencję ogonową, programowanie dynamiczne czy zwykłe użycie stosu, coby zapamiętywać aktualny stan i pozbyć się wywołań rekurencyjnych. Co do przykładów nie do końca wiem, o co pytasz. Tak, da się je napisać ich iteracyjne odpowiedniki, jeśli o to chodzi.

Jack: silnie , fibonacciego i inne tez mozna zarowno iteracyjnie jak i rekurencyjnie

Mariusz: Mógłbyś dokładniej opisać sposoby zapisu algorytmów rekurencyjnych w sposób iteracyjny Co do przykładów to chodzi o to w jaki sposób napisać ich iteracyjne odpowiedniki void procedure(int *A,int l,int r) { int i,j; int x,y; x=A[(l+r)/2]; i=l; j=r; do { while(A[i]<x) i++; while(x<A[j]) j−−; if(i<=j) { y=A[i]; A[i]=A[j]; A[j]=y; i++; j−−; } } while(i<=j); if(l<j) procedure(A,l,j); if(i<r) procedure(A,i,r); } Jak zamienić tę funkcję na jej odpowiednik iteracyjny ? Dobrze by było gdybyś podał jakiś kod z komentarzem

Jack: Wyglada mi na quicksort, wiec rzuce tym: http://www.cs.put.poznan.pl/mmachowiak/QuickSortIter.jpg

Pytający: Też jedynie rzucę linkiem (po co się rozpisywać, gdy ktoś już to zrobił ): https://gist.github.com/TeWu/3675308 (co prawda napisane w Ruby, ale jak dla mnie jest w pełni zrozumiałe bez znajomości składni języka)

Mariusz: No to inny przykład struct Node { int data; struct Node *next; } struct Node* function(struct Node *a,struct Node *b) { struct Node *result=NULL; if(a==NULL) return b; else if(b==NULL) return a; if(a−>data<=b−>data) { result=a; result−>next=function(a−>next,b); } else { result=b; result−>next=function(a,b−>next); } return result; }

Mariusz: Pytający widzę że nie chce ci się opisywać sposobów zapisywania algorytmów rekurencyjnych w sposób iteracyjny Zajrzałbyś do tematu https://matematykaszkolna.pl/forum/353651.html No tutaj raczej w sieci rozwiązania nie znajdziesz aby podesłać odnośnik

Pytający: Takie coś powinno działać tak samo (jak się nie machnąłem): https://pastebin.com/Vm4uMYmb A algorytmu na przerabianie nie znam, więc i nie podam. Czasem trzeba po prostu pokombinować. Jak chcesz jakieś uschematyzowane podejścia, takie dość ciekawe artykuły znalazłem (tym razem to Python , acz jedynie czwarta część (patrząc pobieżnie) zdaje się być specyficzna dla tego języka): http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html http://blog.moertel.com/posts/2013-06-03-recursion-to-iteration-3.html http://blog.moertel.com/posts/2013-06-12-recursion-to-iteration-4-trampolines.html

Pytający: Co do kulek − otwierałem już kiedyś te linki, ale tego kodu aż się czytać nie chce. Z czym konkretnie masz problem?

Mariusz: Jeśli chodzi o kulki to brakuje w nim sprawdzania i usuwania diagonalnych linii w obydwu kierunkach a także zapisu wyniku do pliku Pamiętasz zadanie z ustawianiem ośmiu hetmanów Pola atakowane przez hetmana podobnie się sprawdzało Jeśli chodzi o zapisywanie algorytmów rekurencyjnych to skoro nie znasz ogólnego algorytmu mogą być w miarę dokładne opisane te uschematyzowanych podejścia

Mariusz: Co do tej funkcji z listą to pewien hindus proponuje takie podejście struct Node * sortedMerge(struct Node *p,struct Node *q) { struct Node *new_head=NULL; struct Node *sorting; if(p==NULL) return q; if(q==NULL) return p; if(p!=NULL && q!=NULL) // Czy wobec powyższych warunków ten warunek jest potrzebny ? { if(p−>data<=q−>data) { sorting=p; p=sorting−>next; } else { sorting=q; q=sorting−>next; } } new_head=sorting; while(p!=NULL && q!=NULL) { if(p−>data<=q−>data) { sorting−>next=p; sorting=p; p=sorting−>next; } else { sorting−>next=q; sorting=q; q=sorting; } } if(p==NULL) sorting−>next=q; if(q==NULL) sorting−>next=p; return new_head; } void procedure(int *A,int p,int h) { int l,r,m; int t; l=2*p; r=2*p+1 if(l<=h && A[l]>A[p]) m=l; else m=p; if(r<=h && A[r]>A[m]) m=r; if(m!=p) { t=A[p]; A[p]=A[m]; A[m]=t; procedure(A,m,h) } } Jaką mamy tutaj rekurencję i jak zastąpić ją za pomocą iteracji

: Co do funkcji hindusa: − tak, tamten warunek jest zbędny − w while'u w else powinno być "q=sorting−>next;" − dwa ostatnie if'y można zamienić na if−else, bo w tamtym miejscu jedynie jedna z wartości p, q jest nullem; ewentualnie zamiast tych if'ów można zapisać krócej (acz to też instrukcja warunkowa): sorting−>next=p ? p : q; − jasne, że lepsza wersja od tej mojej ze stosem, bo nie potrzeba pamięci i u mnie są dwie pętle (złożoność pozostaje taka sama, ale większy współczynnik) Co do drugiej funkcji jest to typowa (prawie) rekurencja ogonowa, tj. wywołanie rekurencyjne jest ostatnią instrukcją (jeśli if spełniony, stąd to "prawie"), zatem w ogóle nie trzeba pamiętać obecnego stanu wywołania. Prosto, skutecznie, acz brzydko pozbędziemy się rekurencji zamieniając linijkę: procedure(A,m,h); na: p=h; goto start; // a etykietę start umieszczamy tuż po deklaracji zmiennych lokalnych (trzecia linijka funkcji) Od razu nasuwa się zamiana takiego rozwiązania na pętlę, można np. tak: void procedure(int *A,int p,int h) { int l,r,m,t; while(1) { l=2*p; r=2*p+1 if(l<=h && A[l]>A[p]) m=l; else m=p; if(r<=h && A[r]>A[m]) m=r; if(m==p) return; t=A[p]; A[p]=A[m]; A[m]=t; p=m; } } Tu masz ładnie objaśnione pozbywanie się rekurencji ogonowej: https://stackoverflow.com/questions/310974/what-is-tail-call-optimization/9814654#9814654

Pytający:

Mariusz: − w while'u w else powinno być "q=sorting−>next;" i tak jest popełniłem błąd przy przepisywaniu To podejście ze stosem też jest przydatne bo pokazuje jak pozbyć się rekurencji korzystając ze stosu Wprowadzając zmienną logiczną można pozbyć się nieskończonej pętli Aby nie łamać jej instrukcjami break czy exit Ja do zamiany tej procedury podszedłem tak Zamiast rekurencji dałem pętlę repeat until (W C/C++ ta pętla nazywa się do while) i przed wejściem do warunku if w którym modyfikowana jest wartość p zachowałem tą wartość w dodatkowej zmiennej Można zrezygnować z przechowywania wartości obydwu zmiennych l oraz r i przechowywać tylko jedną zmienną Jeśli po przypisaniu wartości do zmiennych l oraz r przekroczymy zakres typu int to procedura będzie działać nieprawidłowo Skoro pisaliśmy o stosach to pewien koleś napisał funkcje dodającą węzeł i wyświetlającą listę w sposób rekurencyjny struct Node { int data; struct Node *next; }; struct Node *push(struct Node *head,int x) { struct Node *h=NULL; if(head!=NULL) { h=head; h−>next=push(head−>next,x); } else { h=(struct Node*)malloc(sizeof(struct Node)); h−>next=NULL; h−>data=x; } return h; } struct Node *pop(struct Node *head) { struct Node *h=NULL; if(head!=NULL) { if(head−>next==NULL) { free(head); h=NULL; } else { h=head; h−>next=pop(head−>next); } } return h; } void printNodes(struct Node *head) { if(head!=NULL) { printf("%d ",head−>data); printNodes(head−>next); } } Gdybyśmy w przypadku sortowania przez podział chcieli użyć dodatkowej tablicy zamiast stosu to ile pamięci byśmy potrzebowali Pamiętaj że programistę interesuję najbardziej przypadek pesymistyczny

Pytający: Nieskończona pętla niekoniecznie musi być "ble". Jeśli pominąć możliwe optymalizacje kompilatora, może być nawet szybsza, niż zastosowanie flagi. Mając pętlę nieskończoną na końcu mam skok bezwarunkowy na początek pętli, warunek jest sprawdzany jednokrotnie dla każdej iteracji. W przypadku użycia flagi, raz sprawdzasz warunek przed ustawieniem flagi i drugi raz sprawdzasz samą wartość flagi na końcu iteracji. Acz to szczegół i niekoniecznie "zdrowe" podejście (przesadnie wszystko optymalizować pomimo braku takowej potrzeby/kosztem zmniejszenia czytelności kodu). W przypadku sortowania przez podział gdybyśmy chcieli użyć tablicy zamiast stosu potrzebowałbyś nie więcej niż n*sizeof(indexType). Zauważ, że dana wartość indeksu nigdy nie powinna wystąpić na stosie dwukrotnie.

Mariusz: Tak tyle że odkładamy dwa indeksy i przepisując kod z książek Wirtha i Diksa zarezerwowałem dwa razy tyle pamięci

Pytający: Tak, odkładamy po dwa indeksy, ale nigdy nie odkładamy 2 takich samych wartości. Pesymistyczny (pod względem wielkości stosu) przypadek (dla n=8): stos: (0, 7) → stos stos: 0, 7 stos → (0, 7), podziały (0,1) i (2,7) → stos stos: 0, 1, 2, 7 stos → (2, 7), podziały (2,3) i (4,7) → stos stos: 0, 1, 2, 3, 4, 7 stos → (4, 7), podziały (4,5) i (6,7) → stos stos: 0, 1, 2, 3, 4, 5, 6, 7 stos → (6, 7), i nie dzielimy stos: 0, 1, 2, 3, 4, 5 stos → (4, 5), i nie dzielimy stos: 0, 1, 2, 3 stos → (2, 3), i nie dzielimy stos: 0, 1 stos → (0, 1), i nie dzielimy stos: