Iteracja może zastąpić rekurencję?

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ć.

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$

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ę.

$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)$
• $\texttt{while(true):}$
  • $m ← \pop(s)$
  • $\ifop{\empty(s)}$
    • $\texttt{return }m$ (to kończy pętlę)
  • $n ← \pop(s)$
  • $\ifop{n = 0}$
    • $\push(s, m+1)$
  • $\elseif{m=0}$
    • $\push(s, n-1)$
    • $\push(s, 1)$
  • $\elsop$
    • $\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.

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?

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ć.