Usuwanie rekurencji

Newb
2011-10-04 13:49
Newb
0

Wiem, że każdy algorytm może zostać zapisany rekurencyjnie (często we wielu przypadkach jest to prostsze) jak i iteracyjnie. Wersja iteracyjna z reguły jest szybsza.

Jak właściwie należy zabrać się za usuwanie rekurencji: czy projektuje się algorytm od początku czy też są jakieś schematy, sztuczki jakie należy zastosować. I jeśli tak, jak wykazać ich poprawność.

Szczególnie interesuje mnie usuwanie podwójnej rekurencji.

Nie zgodzę się, że rekurencja jest w wielu przypadkach prostsza. - hauleth 2011-10-04 13:54

Pozostało 580 znaków

2011-10-04 13:56

Rejestracja: 16 lat temu

Ostatnio: 16 minut temu

0

Często wystarczy pomyśleć. A sztuczka która zawsze działa dość prosto: implementujesz sobie własny stos / używasz jakiejs kolekcji do przechowywania stosu (z reguły jest to lista jednokierunkowa). Wartości wrzucasz do tej listy a wywołanie rekurencyjne symulujesz przez kolejną iterację pętli. Pod koniec pętli zdejmujesz wartości ze swojego stosu.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2011-10-04 15:01

Rejestracja: 9 lat temu

Ostatnio: 7 lat temu

0

Ogólnie musisz się zastanowić, czy da się przedstawić rekurencję w postaci prostej pętli, jeżeli tak to zmiana jest prosta. Jeżeli nie, to bym tego zwykle nie ruszał, pomysł Shaloma może i jest minimalnie szybszy niż wywoływanie funkcji (choć nie przy użyciu listy jednokierunkowej, tracisz cały wzrost szybkości na alokowaniu pamięci), ale praktycznie odtwarza stos powstający podczas wywoływania funkcji w pamięci i jest to rozwiązanie często mniej czytelne.

Pozostało 580 znaków

2011-10-04 20:21

Rejestracja: 8 lat temu

Ostatnio: 17 godzin temu

0

Niektóre z algorytmów wręcz proszą się o derekursywację (silnia, Fibonacci).
O metodach z tym związanych piszą w:
"Algorytmy i struktury danych", L. Banachowski, K. Diks, W. Rytter
"Algorytmy struktury danych i techniki programowania", Piotr Wróblewski

Najprostszy sposób to alokacja tablicy która przechowuje wartości pośrednie i wykorzystywanie jej w kolejnych wykonaniach iteracji.
Idealny przykład takiego rozwiązania to trójkąt Pascala - można zrobić rekurencyjnie lub nie:
http://in.answers.yahoo.com/q[...]dex?qid=20090206203521AAbKWR7

Edit: to był skrót myślowy. Symbol (n po k) można zrobić rekurencyjnie lub nie. Właśnie dzięki trójkątowi Pascala.

Uproszczonie tego rozwiązania (zamiast tablicy k zmiennych) jest tutaj:
http://pl.wikipedia.org/wiki/Derekursywacja


Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 1x, ostatnio: vpiotr, 2011-10-04 20:28
jakie kurna ładne słowo - Xitami 2011-10-05 01:43

Pozostało 580 znaków

Newb
2011-10-04 22:52
Newb
0

Dzięki.

Pozostało 580 znaków

1 użytkowników online, w tym zalogowanych: 0, gości: 0, botów: 1

Robot: Bingbot