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”?
recursion
computer-science
theory
iteration
Gustavo Carreno
źródło
źródło
Odpowiedzi:
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.
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:
musi zostać zastąpiony przez
Edycja: Artykuł Eliminacja stosów i rekurencji (lub link Tworzenie kopii zapasowej artykułu ) zawiera więcej szczegółów na ten temat.
źródło
(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.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.htmlNaprawdę najczęstszym sposobem na to jest utrzymanie własnego stosu. Oto rekurencyjna funkcja szybkiego sortowania w C:
Oto, w jaki sposób możemy iterować, utrzymując własny stos:
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ł.
źródło
O(N) = O(R*L)
którymL
jest suma złożoności „dla warstwy r”, np. w tym przypadku maszO(N)
pracę na każdym kroku wykonując partycjonowanie, głębokość rekurencyjna jestO(R)
, tj. w najgorszym przypadkuO(N)
, średnia przypadekO(logN)
tutaj.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.
Iteracyjne rozwiązanie:
źródło
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.
źródło
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):
Znając mnie, prawdopodobnie popełniłem błąd w kodzie, ale pomysł już istnieje.
źródło
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ę.
źródło
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.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:
Kod iteracyjny:
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
+++++++++++++++++++++++++
------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
źródło
stackitem
obiektów przypisuje się wartość śmiecira
. Wszystko nadal działa w najbardziej podobnym przypadku, ale przypadkowo powinnora
wynosić 1 lub 2, otrzymasz nieprawidłowe zachowanie. Rozwiązaniem jest zainicjowaniera
na 0.stackitem
nie można przekazywać bez inicjowania. Ale tak, inicjowanie na 0 wychwytuje błędy.v.pop_back()
zestawienie?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.
źródło
Tylko zabijanie czasu ... Funkcja rekurencyjna
można przekonwertować na
źródło
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:
Przemienia się w:
źródło
Myślenie o rzeczach, które faktycznie potrzebują stosu:
Jeśli weźmiemy pod uwagę wzorzec rekurencji jako:
Na przykład klasyczna wieża w Hanoi
Można to przełożyć na pętlę działającą na jawnym stosie, przekształcając go jako:
Dla Tower of Hanoi staje się 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 stosieint
, a nie jeden element na stosieTask
).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ę.
źródło
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:
kończy się wezwaniem do foo. Można to zastąpić:
co eliminuje drugie wywołanie rekurencyjne.
źródło
Pytanie , który został zamknięty jako duplikat ten miał bardzo specyficzną strukturę danych:
Węzeł miał następującą strukturę:
Funkcja usuwania rekurencyjnego wyglądała następująco:
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
child
na końcu listy górnego rzędu.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.
źródło
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!
źródło
Kolejny prosty i kompletny przykład zamiany funkcji rekurencyjnej na iteracyjną przy użyciu stosu.
źródło
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:
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ć.
źródło
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:
źródło
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 .
źródło
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
StackOverflow
dotyczy dużych wartości n:możemy zdefiniować wersję, która używa własnego stosu w następujący sposób:
gdzie
return
jest zdefiniowany jako:Działa to również w przypadku bardziej złożonych funkcji, na przykład funkcji ackermann :
można przekształcić w:
źródło