Czy każdą rekurencję można przekształcić w iterację?

Czy dla każdej funkcji rekurencyjnej zawsze jest możliwe zapisanie postaci nie rekurencyjnej?

Niestety, nie jestem w stanie znaleźć dobrego, formalnego definicja GOTO online więc oto jeden:

Program GOTO jest sekwencją poleceń P wykonywaną na maszynie rejestrującej taką, że P jest jedną z następujących:

• HALT, co wstrzymuje egzekucję
• r = r + 1 Gdzie r jest dowolnym rejestrem
• r = r – 1 Gdzie r jest dowolnym rejestrem
• GOTO x Gdzie x jest etykietą
• IF r ≠ 0 GOTO x gdzie r jest dowolnym rejestrem, a x jest etykietą
• etykieta, po której następuje którykolwiek z powyższych polecenia.

Jednak konwersje między funkcjami rekurencyjnymi i nie-rekurencyjnymi nie zawsze są trywialne (z wyjątkiem bezmyślnej ręcznej re-implementacji stosu wywołań).

Rekurencja jest implementowana jako stosy lub podobne konstrukcje w rzeczywistych interpreterach lub kompilatorach. Więc z pewnością można przekonwertować funkcję rekurencyjną na iteracyjny odpowiednik , ponieważ zawsze tak się robi (Jeśli automatycznie). Będziesz po prostu powielał pracę kompilatora w ad-hoc i prawdopodobnie w bardzo brzydki i nieefektywny sposób.

Zasadniczo tak, w istocie to, co musisz zrobić, to zastąpić wywołania metod (które domyślnie wypychają stan na stos) w Jawne wypychania stosu, aby zapamiętać, gdzie doszło do 'poprzedniego wywołania', a następnie wykonać 'wywołaną metodę'.

Wyobrażam sobie, że kombinacja pętli, stosu i maszyny stanowej może być użyta we wszystkich scenariuszach poprzez symulowanie wywołań metod. Czy to będzie "lepsze" (albo szybsze, albo wydajniejsze w jakiś sens) nie da się powiedzieć w ogóle.

Tak, używanie jawnie stosu (ale rekurencja jest o wiele przyjemniejsza do odczytania, IMHO).

• Rekurencyjny przepływ wykonywania funkcji może być reprezentowany jako drzewo.

• Ta sama logika może być wykonana przez pętlę, która wykorzystuje strukturę danych do przemierzania tego drzewa.

• Depth-first traversal można wykonać za pomocą stosu, width-First traversal można wykonać za pomocą kolejki.

Czy każda rekurencja może być wykonana w pojedynczej pętli? Tak., ponieważ

Maszyna Turinga robi wszystko, co robi, wykonując pojedynczą pętlę:

1. Pobierz instrukcję,
2. Oceń to,
Goto 1.

Tak, zawsze można napisać wersję Nie rekurencyjną. Trywialnym rozwiązaniem jest użycie struktury danych stosu i symulowanie rekurencyjnego wykonania.

W zasadzie zawsze jest możliwe usunięcie rekursji i zastąpienie jej iteracją w języku, który ma nieskończony stan zarówno dla struktur danych, jak i dla stosu wywołań. Jest to podstawowa konsekwencja tezy Churcha-Turinga.

Biorąc pod uwagę rzeczywisty język programowania, odpowiedź nie jest tak oczywista. Problem polega na tym, że całkiem możliwe jest posiadanie języka, w którym ilość pamięci, która może być przydzielona w programie, jest ograniczona, ale gdzie ilość stosu połączeń, które mogą być używany jest nieograniczony(32-bitowy C, gdzie adres zmiennych stosu nie jest dostępny). W tym przypadku rekurencja jest potężniejsza, ponieważ ma więcej pamięci, z której może korzystać; nie ma wystarczającej ilości pamięci przeznaczonej na emulację stosu wywołań. Aby uzyskać szczegółową dyskusję na ten temat, zobacz ta dyskusja .

Czasami zastąpienie rekursji jest znacznie łatwiejsze. Rekurencja była modną rzeczą nauczaną w CS w latach 90-tych, więc wielu przeciętnych programistów z tamtych czasów uznało, że jeśli rozwiązujesz coś za pomocą rekurencji, to będzie to lepsze rozwiązanie. Więc użyliby rekurencji zamiast zapętlania do tyłu, aby odwrócić kolejność, lub takich głupich rzeczy. Czasami więc usuwanie rekursji jest prostym ćwiczeniem typu "duh, to było oczywiste".

Jest to teraz mniejszy problem, ponieważ Moda przesunęła się w kierunku innych technologii.

Wszystkie funkcje obliczeniowe mogą być obliczane przez maszyny Turinga i stąd systemy rekurencyjne i maszyny Turinga (systemy iteracyjne) są równoważne.

Usunięcie rekurencji jest złożonym problemem i jest możliwe w dobrze zdefiniowanych okolicznościach.

Poniższe przypadki należą do łatwych:

• rekurencja ogona
• bezpośrednia rekurencja liniowa

Appart ze stosu jawnego, innym wzorcem konwersji rekursji na iterację jest użycie trampoliny.

Tutaj funkcje zwracają wynik końcowy lub zamknięcie wywołania funkcji, które w przeciwnym razie by wykonało. Następnie funkcja inicjująca (trampolining) wywołuje zwracane zamknięcia aż do osiągnięcia ostatecznego wyniku.

To podejście działa dla wzajemnie rekurencyjnych funkcji, ale obawiam się, że działa tylko dla ogony.

Http://en.wikipedia.org/wiki/Trampoline_ (komputery)

Powiedziałbym tak - wywołanie funkcji jest niczym innym jak Goto i operacją stosu (z grubsza rzecz biorąc). Wszystko, co musisz zrobić, to naśladować stos zbudowany podczas wywoływania funkcji i zrobić coś podobnego jak goto (możesz naśladować Goto z językami, które nie mają tego słowa kluczowego).

Przyjrzyj się poniższym wpisom na Wikipedii, możesz je wykorzystać jako punkt wyjścia do znalezienia pełnej odpowiedzi na swoje pytanie.

• Rekurencja w informatyce
• Relationship

Następuje akapit, który może dać Ci podpowiedź, od czego zacząć:

Rozwiązanie relacji nawrotowej oznacza otrzymanie rozwiązania postaci zamkniętej : nie-rekurencyjnej funkcji n.

Zobacz też paragraf tej pozycji .

Możliwe jest przekształcenie dowolnego algorytmu rekurencyjnego na nie rekurencyjny jeden, ale często logika jest znacznie bardziej złożona i wymaga użycie stosu. W rzeczywistości sama rekurencja używa stosu: stos funkcji.

Więcej Szczegółów: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

Tazzego, rekurencja oznacza, że funkcja wywoła się, czy ci się to podoba, czy nie. Kiedy ludzie mówią o tym, czy rzeczy można zrobić bez rekurencji, mają to na myśli i nie można powiedzieć" nie, to nie jest prawda, ponieważ nie zgadzam się z definicją rekurencji " jako ważnego stwierdzenia.

Mając to na uwadze, prawie wszystko inne, co mówisz, jest nonsensem. Jedyną inną rzeczą, którą mówisz, że nie jest nonsensem, jest pomysł, że nie wyobrażasz sobie programowania bez połączenia. To jest coś, co było robione przez dziesięciolecia, dopóki korzystanie z callstack stało się popularne. Stare wersje FORTRANA nie posiadały callstacka i działały bez zarzutu.

Nawiasem mówiąc, istnieją języki Turinga-kompletne, które implementują tylko rekurencję (np. SML) jako sposób zapętlania. Istnieją również języki Turinga-kompletne, które implementują tylko iterację jako sposób zapętlania (np. FORTRAN IV). Teza Churcha-Turinga dowodzi, że wszystko możliwe w rekurencji-tylko języki mogą być wykonywane w języku Nie rekurencyjnym i vica-versa przez fakt, że oba mają własność Turinga-zupełności.

Oto algorytm iteracyjny:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end

Pytanie: jeśli jako pierwsza rzecz funkcja tworzy kopię siebie w losowej przestrzeni pamięci pustej, a następnie zamiast wywoływać samą siebie wywołaj kopię, to czy jest to nadal rekurencja?(1) powiedziałbym, że tak.

Czy jawne użycie stosu jest prawdziwym sposobem na usunięcie rekursji? (2) powiedziałbym nie. Zasadniczo, czy nie naśladujemy tego, co się dzieje, gdy używamy jawnie rekurencji? Uważam, że nie możemy zdefiniować rekurencji po prostu jako "funkcji, która sama się wywołuje" , ponieważ widzę rekurencję również w "kodzie kopiowania "(1) oraz w " jawnym użyciu stosu "(2).

Co więcej, nie widzę, jak CT demonstruje, że wszystkie algorytmy rekurencyjne mogą stać się iteracyjne. Wydaje mi się tylko, że "wszystko" posiadające " moc " maszyny Turinga może wyrazić wszystkie algorytmy, które może wyrazić. Jeśli maszyna Turinga nie może rekurencji, jesteśmy pewni, że każdy rekurencyjny algo ma swoje interatywne tłumaczenie... Maszyna Turinga może rekurencyjnie? Według mnie, jeśli da się ją "zaimplementować" (dowolnie), to możemy powiedz, że to ma. Naprawdę? Nie wiem.

Wszystkie prawdziwe procesory, które znam, mogą być rekurencyjne. Szczerze mówiąc, nie widzę, jak programować na serio bez posiadania stosu wywołań, i myślę, że to jest to, co sprawia, że rekurencja jest możliwa najpierw.

Unikając kopiowania (1) i "imitowanego stosu" (2), czy udowodniliśmy, że każdy rekurencyjny algo może być wyrażony iteracyjnie na maszynach rzeczywistych?! Nie widzę, gdzie to pokazaliśmy.