Usuwanie rekurencji

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.

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.

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.

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/question/index?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

0

Dzięki.

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