wzorce projektowe dla konwersji rekurencyjnych algorytmów iteracyjnych do nich

Question

Czy istnieją jakieś ogólne heurystyka, porady, wskazówki lub paradygmaty wspólnego projektu, które mogą być stosowane do konwersji algorytmu rekurencyjnego do iteracyjnego jednego? Wiem, że da się to zrobić, zastanawiam się, czy istnieją praktyki, o których warto pamiętać.

Answer 1

często można całkowicie zachować oryginalną strukturę algorytmu rekurencyjnego, ale uniknąć stosu, stosując ogon połączenia i zmiana na kontynuacja - przekazanie, zgodnie z sugestią this blog entry. (Powinienem naprawdę ugotować lepszy samodzielny przykład.)

Answer 2

Jeden wzór jest Tail Recursion:

Wywołanie funkcji jest uważane za ogon rekurencyjne jeśli nie ma nic do zrobienia po powrocie funkcji, poza zwraca jego wartość.

Wiki.

Answer 3

Wystarczy popatrzeć na te linki do przykładów wykonania

Recursion VS Iteration (Looping) : Speed & Memory Comparison

i

Replace Recursion with Iteration

i

Recursion vs Iteration

P: Czy wersja rekursyjna jest zwykle szybsza? ? A: Nie - to jest wolniejsze (ze względu na napowietrznej utrzymania stos)

Q: Does the recursive version usually use less memory? 
    A: No -- it usually uses more memory (for the stack). 

    Q: Then why use recursion?? 
    A: Sometimes it is much simpler to write the recursive version (but 

musimy czekać aż mamy omawianych drzew, aby zobaczyć naprawdę dobre przykłady ...)

Answer 4

Powszechną praktyką jest zarządzać stos LIFO, który utrzymuje listę obrotowej co „pozostaje do zrobienia” i obsługiwać cały proces w pętli while, która trwa aż lista jest pusta.
Z tego wzoru, co byłoby wywołanie rekurencyjne w prawdziwym modelu rekurencji zastępuje
- pchanie od „kontekstu” prądu (Częściowo wykończona) Zadanie jest na stosie,
- pchanie nowego zadania (jeden, który spowodował rekursję) na stosie
- i "kontynuować" (tj. przeskoczyć na początek) pętli while. W pobliżu głowy pętli, logika wyskakuje ostatnio wstawiony kontekst i rozpoczyna pracę na tej podstawie.

Skutecznie to tylko "porusza" informacje, które w przeciwnym razie byłyby przechowywane w zagnieżdżonych ramkach stosu na stosie "systemowym" do kontenera stosu zarządzanego przez aplikację. Jest to jednak poprawa, ponieważ ten kontener stosu może być przydzielony w dowolnym miejscu (limit rekursji jest zwykle powiązany z limitami w stosie "systemowym"). Zasadniczo ta sama praca zostaje wykonana, ale wyraźne zarządzanie "stosem" pozwala na to, aby odbywało się to w konstrukcji z jedną pętlą, a nie rekurencyjnymi.

Answer 5

Powszechnie stosowaną techniką, której używam w procesie zamiany rekursywnego algorytmu przez iteracyjny, jest zwykle użycie stosu, przesuwając parametry, które są przekazywane do funkcji rekursywnej.

Sprawdź następujące artykuły:

• Replacing Recursion With a Stack
• Stacks and Recursion Elimination (pdf)

Answer 6

Często rekursję ogólną można zastąpić rekurencją ogona, zbierając częściowe wyniki w akumulatorze i przekazując je w dół za pomocą wywołania rekursywnego. Rekursja ogona jest w zasadzie iteracyjna, rekursywne wywołanie może być realizowane jako skok.

Na przykład, średnia ogólna rekurencyjne definicja czynnikowej

factorial(n) = if n = 0 then 1 else n * factorial(n - 1) 

może być zastąpiony przez

factorial(n) = f_iter(n, 1) 

i

f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a) 

która ogon rekurencyjne. To jest taka sama jak

a = 1; 
while (n != 0) { 
    a = n * a; 
    n = n - 1; 
} 
return a; 

Answer 7

ja zazwyczaj zaczynają się od sprawy podstawowej (każda funkcja rekurencyjna posiada) i pracować moją drogę do tyłu, przechowywanie wyników w pamięci podręcznej (tablica lub Hashtable) w razie potrzeby.

Twoja funkcja rekursywna rozwiązuje problem, rozwiązując mniejsze podproblemy i wykorzystując je do rozwiązania większej instancji problemu. Każdy podproblem jest również dzielony dalej i tak dalej, aż podproblem jest tak mały, że rozwiązanie jest trywialne (to jest w przypadku podstawowym).

Chodzi o to, aby rozpocząć od przypadku podstawowego (lub przypadków podstawowych) i użyć go do zbudowania rozwiązania dla większych skrzynek, a następnie użyć ich do zbudowania jeszcze większych skrzynek i tak dalej, aż cały problem zostanie rozwiązany. To nie wymaga stosu i może być wykonane z pętlami.

Prosty przykład (w Pythonie):

#recursive version 
def fib(n): 
    if n==0 or n==1: 
      return n 
    else: 
      return fib(n-1)+fib(n-2) 

#iterative version 
def fib2(n): 
    if n==0 or n==1: 
      return n 
    prev1,prev2=0,1 # start from the base case 
    for i in xrange(n): 
      cur=prev1+prev2 #build the solution for the next case using the previous solutions 
      prev1,prev2=cur,prev1 
    return cur