Iteracja może zastąpić rekurencję?

42

Widziałem przepełnienie całego stosu, np. Tutaj , tutaj , tutaj , tutaj , tutaj i kilku innych, których nie chcę wspominać, że „każdy program, który korzysta z rekurencji, można przekonwertować na program wykorzystujący tylko iterację”.

Był nawet wysoko oceniany wątek z bardzo pozytywną odpowiedzią, która powiedziała, że tak, to możliwe.

Teraz nie mówię, że się mylą. Po prostu ta odpowiedź jest sprzeczna z moją skromną wiedzą i zrozumieniem na temat komputerów.

Wierzę, że każdą funkcję iteracyjną można wyrazić jako rekurencję, a wikipedia ma takie oświadczenie. Wątpię jednak, by odwrotność była prawdziwa. Po pierwsze, wątpię, by nieprymitywne funkcje rekurencyjne można było wyrazić iteracyjnie.

Wątpię również, aby hiperoperacje można wyrazić iteracyjnie.

W swojej odpowiedzi (której nie rozumiem przy okazji) na moje pytanie @YuvalFIlmus powiedział, że nie jest możliwe przekształcenie żadnej sekwencji operacji matematycznych w sekwencję dodatków.

Jeśli odpowiedź YF jest rzeczywiście poprawna (tak mi się wydaje, ale jego rozumowanie było ponad moją głową), to czy nie oznacza to, że nie każdą rekurencję można przekształcić w iterację? Ponieważ gdyby można było przekonwertować każdą rekurencję na iterację, byłbym w stanie wyrazić wszystkie operacje jako sekwencję dodatków.

Moje pytanie brzmi:

Czy każdą rekurencję można przekonwertować na iterację i dlaczego?

Proszę dać odpowiedź jasnemu liceum lub studentowi pierwszego roku zrozumie. Dziękuję Ci.

PS Nie wiem, co to jest prymitywna rekurencja (wiem o funkcji Ackermanna, i że nie jest to prymitywna rekurencja, ale wciąż można ją obliczyć. ALL cała moja wiedza na jej temat pochodzi ze strony Wikipedii na temat funkcji Ackermanna.)

PPS: Jeśli odpowiedź brzmi „tak”, czy mógłbyś na przykład napisać iteracyjną wersję funkcji innej niż pierwotna-rekurencyjna. Np. Ackermann w odpowiedzi. Pomoże mi to zrozumieć.

computability recursion iteration

— Tobi Alafin
źródło

21

Wszystko, co uruchamiasz na procesorze, jest iteracyjne. Możesz napisać go rekurencyjnie w języku wyższego rzędu, ale i tak zostanie on skompilowany w kilka iteracyjnych instrukcji asemblera. Tak więc dosłownie, kompilator robi dokładnie to, o co prosisz, konwertuje całą Twoją fantazyjną rekurencję na kilka iteracyjnych instrukcji dla procesora.

— Davor,

6

Na niskim poziomie większość z nas wie, że rekurencja to iteracja plus stos. Bezkontekstowa rekurencja modelu gramatyki, podczas gdy automaty wypychające są iteracyjnymi „programami” z pamięcią stosu.

— Hendrik Jan

2

Wskazując, że ogólnie dobrym pomysłem jest odczekanie co najmniej 24 godzin, aby zobaczyć, czy pojawią się inne odpowiedzi. Przyjęte pytanie wydaje mi się dość długie i zawiłe, szczerze mówiąc, i wydaje się, że celowo komplikuje sprawy bardziej niż to konieczne. Podstawowa odpowiedź na twoje pytanie brzmi: „stos użyty do rekurencji może być jawnie zaimplementowany w sposób iteracyjny” i nie musi być o wiele bardziej skomplikowany. Rozważania o tym, czy pamięć jest nieograniczona, czy nie, nie wchodzą w grę, ponieważ ta funkcja jest niezbędna także w przypadku stosów rekurencyjnych.

— AnoE,

możliwe jest wdrożenie emulatora maszyny Turinga z tylko iteracją

— Sarge Borsch

W klasie języków porównawczych, którą odbyłem dawno temu, musieliśmy napisać funkcję Ackermanna w asemblerze, w FORTRAN (nie współczesnym Fortranie) i w wybranym przez siebie języku rekurencyjnym. Tak, jest to możliwe w praktyce. I oczywiście jest to możliwe w teorii. Zobacz na przykład pytanie, które dowodzi, że maszyny Turinga i rachunek lambda są równoważne .

— David Hammen

52

Możliwe jest zastąpienie rekurencji iteracją i nieograniczoną pamięcią .

Jeśli masz tylko iterację (powiedzmy pętle while) i skończoną ilość pamięci, to wszystko, co masz, to automat skończony. Przy skończonej ilości pamięci obliczenia mają skończoną liczbę możliwych kroków, więc można je symulować za pomocą skończonego automatu.

Po nieograniczonej pamięci zmienia ofertę. Ta nieograniczona pamięć może przybierać wiele form, które okazują się mieć równoważną moc ekspresyjną. Na przykład maszyna Turinga upraszcza: jest pojedyncza taśma, a komputer może przesuwać się do przodu lub do tyłu na taśmie tylko o jeden krok na raz - ale to wystarczy, aby zrobić wszystko, co można zrobić za pomocą funkcji rekurencyjnych.

Maszynę Turinga można postrzegać jako wyidealizowany model komputera (maszyna skończona) z dodatkową pamięcią, która rośnie na żądanie. Zauważ, że ważne jest, aby nie tylko nie było skończonego wiązania na taśmie, ale nawet biorąc pod uwagę dane wejściowe, nie można wiarygodnie przewidzieć, ile taśmy będzie potrzebne. Jeśli potrafisz przewidzieć (tj. Obliczyć), ile taśmy potrzeba na wejściu, możesz zdecydować, czy obliczenia zostaną zatrzymane, obliczając maksymalny rozmiar taśmy, a następnie traktując cały system, w tym również taśmę skończoną, jako maszynę skończoną .

Inny sposób symulacji maszyny Turinga z komputerami jest następujący. Symuluj maszynę Turinga za pomocą programu komputerowego, który przechowuje początek taśmy w pamięci. Jeśli obliczenia dojdą do końca części taśmy, która mieści się w pamięci, wymień komputer na większy i ponownie uruchom obliczenia.

Załóżmy teraz, że chcesz symulować obliczenia rekurencyjne z komputerem. Techniki wykonywania funkcji rekurencyjnych są dobrze znane: każde wywołanie funkcji ma pamięć, zwaną ramką stosu . Co najważniejsze, funkcje rekurencyjne mogą propagować informacje poprzez wiele wywołań poprzez przekazywanie zmiennych. Pod względem implementacji na komputerze oznacza to, że wywołanie funkcji może uzyskać dostęp do ramki stosu wywołania (grand) ^* rodzica.

Komputer jest procesorem - skończoną maszyną stanów (z ogromną liczbą stanów, ale tutaj robimy teorię obliczeń, więc liczy się tylko to, że jest skończona) - w połączeniu ze skończoną pamięcią. Mikroprocesor działa jeden gigantyczny pętla while: „gdy zasilanie jest włączone, przeczytaj instrukcję z pamięci i wykonaj ją”. (Rzeczywiste procesory są znacznie bardziej skomplikowane, ale nie wpływa to na to, co mogą obliczyć, tylko na to, jak szybko i wygodnie to robią.) Komputer może wykonywać funkcje rekurencyjne za pomocą tej pętli while, aby zapewnić iterację, a także mechanizm dostęp do pamięci, w tym możliwość dowolnego zwiększania rozmiaru pamięci.

Jeśli ograniczysz rekurencję do prymitywnej rekurencji, możesz ograniczyć iterację do iteracji ograniczonej . Oznacza to, że zamiast używać pętli while z nieprzewidywalnym czasem działania, możesz używać pętli, w których liczba iteracji jest znana na początku pętli¹. Liczba iteracji może nie być znana na początku programu: sama mogła zostać obliczona na podstawie poprzednich pętli.

Nie zamierzam tu nawet szkicować dowodu, ale istnieje intuicyjny związek między przejściem od prymitywnej rekurencji do pełnej rekurencji, a przejściem od pętli do pętli while: w obu przypadkach wymaga to wcześniejszej wiedzy, kiedy zatrzymać. Przy pełnej rekurencji odbywa się to za pomocą operatora minimalizacji, gdzie kontynuujesz, aż znajdziesz parametr, który spełnia warunek. W przypadku pętli while odbywa się to do momentu spełnienia warunku pętli.

_{forwhile $n$}

— Gilles „SO- przestań być zły”
źródło

Przyjmowanie szczegółowych wyjaśnień, utrzymywane na żądanym poziomie.

— Tobi Alafin,

12

Myślę, że warto zauważyć, niż w prawdziwych komputerach, rekurencja zużywa również pamięć (rosnący stos wywołań). Tak więc w praktycznych zastosowaniach nie ma wymogu nieograniczonej pamięci (ponieważ wszystko jest przez nią jednakowo ograniczone). A rekurencja często wymaga więcej pamięci niż iteracji.

— Agent_L,

@Agent_L Tak, rekurencja potrzebuje nieograniczonej pamięci do przechowywania wszystkich ramek stosu. Przy podejściu rekurencyjnym istnieje wymóg nieograniczonej pamięci, ale nie można jej intuicyjnie oddzielić od sekwencjonowania operacji, takich jak iteracje.

— Gilles „SO- przestań być zły”

1

Być może interesujące byłyby tezy Kościoła Turinga. Maszyny Turinga są urządzeniami wysoce iteracyjnymi bez (nieodłącznej) koncepcji rekurencji. Rachunek lambda jest językiem opracowanym do wyrażania obliczeń w sposób rekurencyjny. Teza Church-Turinga pokazała, że wszystkie wyrażenia lambda można ocenić na maszynie Turinga, łącząc rekurencję i iterację.

— Cort Ammon,

1

@BlackVegetable Jeśli metoda rekurencyjna nie ma wewnętrznych zmiennych, a jedyną używaną przez nią pamięcią jest stos wywołań (co można zoptymalizować za pomocą TCO), to jej wersja iteracyjna najprawdopodobniej również nie będzie miała wewnętrznych zmiennych i będzie używać tylko stałej ilości pamięci ( zmienne) wspólne dla wszystkich iteracji, takich jak licznik.

— Agent_L

33

Każda rekurencja może być przekształcona w iterację, o czym świadczy procesor, który wykonuje dowolne programy za pomocą nieskończonej iteracji fetch-execute. Jest to forma twierdzenia Böhm-Jacopini . Ponadto wiele kompletnych modeli obliczeniowych Turinga nie ma rekurencji, na przykład maszyny Turinga i maszyny liczące .

Prymitywne funkcje rekurencyjne odpowiadają programom używającym ograniczonej iteracji, to znaczy, musisz określić liczbę iteracji, w których pętla jest wykonywana wcześniej. Ograniczona iteracja nie może ogólnie symulować rekurencji, ponieważ funkcja Ackermanna nie jest prymitywną rekurencją. Ale nieograniczona iteracja może symulować dowolną częściowo obliczalną funkcję.

— Yuval Filmus
źródło

25

$a(n,m)$

$s$

$\DeclareMathOperator{\push}{push}\push(s, x)$ $x$ $\DeclareMathOperator{\pop}{pop} x ← \pop(s)$ $\DeclareMathOperator{\empty}{empty}\empty(s)$

$\texttt{Ackermann}(n_0, m_0):$ $\def\ifop#1{\texttt{if(}#1\texttt{):}}$ $\def\elseif#1{\texttt{else if(}#1\texttt{):}}$ $\def\elsop{\texttt{else:}}$

$s = \emptyset$ (zainicjuj pusty stos)
$\push(s,n_0)$
$\push(s,m_0)$
- $m ← \pop(s)$
- - $\texttt{return }m$ (to kończy pętlę)
- $n ← \pop(s)$
- - $\push(s, m+1)$
- - $\push(s, n-1)$
  - $\push(s, 1)$
- - $\push(s, n-1)$
  - $\push(s, n)$
  - $\push(s, m-1)$

Zaimplementowałem to na Cejlonie, jeśli chcesz, możesz uruchomić go na stronie internetowej . (Wysyła stos na początku każdej iteracji pętli.)

Oczywiście to właśnie przeniosło stos niejawnego wywołania z rekurencji do jawnego stosu z parametrami i zwracanymi wartościami.

— Paŭlo Ebermann
źródło

15

Myślę, że to ważna kwestia. Dość wyraźnie pokazałeś, że rekurencja nie jest niczym specjalnym i że można ją usunąć po prostu śledząc stos wywołań, zamiast pozwolić kompilatorowi to zrobić. Rekurencja to tylko funkcja kompilatora, która ułatwia pisanie tego rodzaju programów.

— David Richerby

4

Dziękujemy za podjęcie wysiłku napisania żądanego programu.

— Tobi Alafin

16

Istnieją już świetne odpowiedzi (z którymi nie mogę nawet konkurować), ale chciałbym przedstawić to proste wyjaśnienie.

Rekurencja to tylko manipulacja stosem środowiska wykonawczego. Recursing dodaje nową ramkę stosu (dla nowego wywołania funkcji rekurencyjnej), a powrót zwraca ramkę stosu (dla właśnie ukończonej innowacji funkcji rekurencyjnej). Rekurencja spowoduje dodanie / usunięcie pewnej liczby ramek stosu, aż w końcu wszystkie one zakończą się (mam nadzieję!), A wynik zostanie zwrócony do osoby dzwoniącej.

Co by się stało, gdybyś utworzył własny stos, zastąpił wywołania funkcji rekurencyjnych wypychaniem stosu, zastąpił zwracanie funkcji rekurencyjnych poppingiem stosu i miałby pętlę while, która działała, aż stos był pusty?

— Alexander
źródło

2

O ile mogę stwierdzić i z własnego doświadczenia, każdą rekurencję można zaimplementować jako iterację. Jak wspomniano powyżej, rekurencja używa stosu, który jest koncepcyjnie nieograniczony, ale praktycznie ograniczony (czy kiedykolwiek dostałeś wiadomość o przepełnieniu stosu?). Na początku programowania (w trzecim kwartale ubiegłego stulecia ostatniego tysiąclecia) korzystałem z języków nierekurencyjnych implementujących algorytmy rekurencyjne i nie miałem problemów. Nie jestem jednak pewien, jak to udowodnić.

— Louis Giokas
źródło