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

Wątek reddit wychowany pozornie ciekawe pytanie:

Funkcje rekurencyjne typu tail można w prosty sposób przekształcić w funkcje iteracyjne. Inne można przekształcić za pomocą jawnego stosu. Czy każdą rekurencję można przekształcić w iterację?

Przykład (licznik?) W poście to para:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Czy zawsze możesz zamienić funkcję rekurencyjną na iteracyjną? Tak, absolutnie, a teza Kościoła Turinga dowodzi, że pamięć służy. Mówiąc ogólnie, stwierdza, że ​​to, co można obliczać za pomocą funkcji rekurencyjnych, można obliczać za pomocą modelu iteracyjnego (takiego jak maszyna Turinga) i odwrotnie. Teza nie mówi ci dokładnie, jak wykonać konwersję, ale mówi, że jest to zdecydowanie możliwe.

W wielu przypadkach konwersja funkcji rekurencyjnej jest łatwa. Knuth oferuje kilka technik w „Sztuce programowania komputerowego”. Często rzecz obliczana rekurencyjnie może być obliczana przy użyciu zupełnie innego podejścia w krótszym czasie i przestrzeni. Klasycznym tego przykładem są liczby Fibonacciego lub ich sekwencje. Z pewnością spotkałeś ten problem w swoim planie studiów.

Z drugiej strony tej monety możemy z pewnością wyobrazić sobie system programowania tak zaawansowany, aby traktować rekurencyjną definicję formuły jako zaproszenie do zapamiętania wcześniejszych wyników, oferując w ten sposób korzyści prędkości bez kłopotu z informowaniem komputera, które kroki należy wykonać wykonaj obliczenia formuły z definicją rekurencyjną. Dijkstra prawie na pewno wymyślił taki system. Spędził dużo czasu próbując oddzielić implementację od semantyki języka programowania. Z drugiej strony, jego niedeterministyczne i wieloprocesowe języki programowania znajdują się w lidze ponad ćwiczącym profesjonalnym programistą.

W końcowej analizie wiele funkcji jest po prostu łatwiejszych do zrozumienia, czytania i pisania w formie rekurencyjnej. O ile nie ma ważnego powodu, prawdopodobnie nie powinieneś (ręcznie) konwertować tych funkcji do jawnie iteracyjnego algorytmu. Twój komputer poprawnie obsłuży to zadanie.

Widzę jeden ważny powód. Załóżmy, że masz prototypowy system w języku wysokiego poziomu, takim jak [ zakładanie bielizny z azbestu ] Scheme, Lisp, Haskell, OCaml, Perl lub Pascal. Załóżmy, że warunki są takie, że potrzebujesz implementacji w C lub Javie. (Być może jest to polityka.) Wtedy z pewnością można by napisać rekursywnie niektóre funkcje, które, dosłownie przetłumaczone, mogłyby zniszczyć twój system wykonawczy. Na przykład, nieskończona rekurencja ogona jest możliwa na Schemacie, ale ten sam idiom powoduje problem w istniejących środowiskach C. Innym przykładem jest użycie funkcji zagnieżdżonych leksykalnie i zakresu statycznego, które Pascal obsługuje, ale C nie.

W tych okolicznościach możesz spróbować przezwyciężyć polityczny opór wobec oryginalnego języka. Może się zdarzyć, że źle wdrażasz Lisp, tak jak w dziesiątym prawie Greenspuna (z przymrużeniem oka). Lub możesz po prostu znaleźć zupełnie inne podejście do rozwiązania. Ale w każdym razie jest na pewno sposób.

Czy zawsze jest możliwe napisanie formularza nierekurencyjnego dla każdej funkcji rekurencyjnej?

Tak. Prostym formalnym dowodem jest wykazanie, że zarówno rekurencja µ, jak i rachunek nierekurencyjny, taki jak GOTO, są całkowicie zakończone przez Turinga. Ponieważ wszystkie rachunki całkowite Turinga są ściśle równoważne pod względem mocy ekspresyjnej, wszystkie funkcje rekurencyjne mogą być realizowane przez nierekurencyjny rachunek całkowy Turinga.

Niestety nie jestem w stanie znaleźć dobrej, formalnej definicji GOTO online, więc oto jedna:

Program GOTO to sekwencja poleceń P wykonywanych na maszynie rejestru, tak że P jest jedną z następujących czynności:

• HALT, co zatrzymuje wykonanie
• r = r + 1gdzie rjest dowolny rejestr
• r = r – 1gdzie rjest dowolny rejestr
• GOTO xgdzie xjest etykieta
• IF r ≠ 0 GOTO xgdzie rjest dowolny rejestr i xjest etykietą
• Etykieta, po której następuje dowolne z powyższych poleceń.

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

Aby uzyskać więcej informacji, zobacz tę odpowiedź .

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

Zasadniczo tak, w gruncie rzeczy to, co ostatecznie musisz zrobić, to zastąpić wywołania metod (które domyślnie wypychają stan na stos) do jawnych wypychań stosów, aby zapamiętać, do czego doszło „poprzednie wywołanie”, a następnie wykonać „wywoływaną metodę” zamiast.

Wyobrażam sobie, że kombinacja pętli, stosu i automatu stanów mogłaby być użyta we wszystkich scenariuszach poprzez podstawową symulację wywołań metod. To, czy będzie to „lepsze” (albo szybsze, albo w pewnym sensie bardziej wydajne), nie jest w ogóle możliwe do powiedzenia.

• Przepływ wykonania funkcji rekurencyjnej może być reprezentowany jako drzewo.

• Tę samą logikę można wykonać za pomocą pętli, która wykorzystuje strukturę danych do przechodzenia przez to drzewo.

• Przechodzenie przez głębokość pierwszą można wykonać za pomocą stosu, pierwsze przejście przez głębokość można wykonać za pomocą kolejki.

Odpowiedź brzmi: tak. Dlaczego: https://stackoverflow.com/a/531721/2128327 .

Czy można wykonać rekurencję w jednej pętli? Tak ponieważ

maszyna Turinga robi wszystko, wykonując jedną pętlę:

1. pobrać instrukcję,
2. oceń to,
3. Goto 1.

Tak, używając jawnie stosu (ale rekursja jest o wiele przyjemniejsza do czytania, IMHO).

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

Zasadniczo zawsze można usunąć rekurencję i zastąpić ją iteracją w języku, który ma nieskończony stan zarówno dla struktur danych, jak i stosu wywołań. Jest to podstawowa konsekwencja tezy Kościoła-Turinga.

Biorąc pod uwagę faktyczny 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órą można przydzielić w programie, jest ograniczona, ale gdzie stos stosu wywołań jest nieograniczony (32-bitowy C, gdzie adres zmiennych stosu nie jest dostępne). W tym przypadku rekurencja jest silniejsza po prostu dlatego, że ma więcej pamięci, której może użyć; nie ma wystarczającej ilości pamięci do przydzielenia, aby emulować stos wywołań. Aby uzyskać szczegółową dyskusję na ten temat, zobacz tę dyskusję .

Wszystkie funkcje obliczalne mogą być obliczane przez maszyny Turinga, a zatem systemy rekurencyjne i maszyny Turinga (systemy iteracyjne) są równoważne.

Czasami zastąpienie rekurencji jest znacznie łatwiejsze. Rekurencja była modną rzeczą nauczaną w CS w latach 90., więc wielu przeciętnych programistów od tego czasu doszło do wniosku, że jeśli rozwiązałeś coś z rekurencją, było to lepsze rozwiązanie. Więc użyliby rekurencji zamiast pętli do tyłu, aby odwrócić kolejność, lub głupich rzeczy tego typu. Czasami więc usunięcie rekurencji jest prostym „ćwiczeniem, to było oczywiste” rodzaj ćwiczeń.

Teraz jest to mniejszy problem, ponieważ moda zmieniła się na inne technologie.

Usuwanie rekurencji jest złożonym problemem i jest wykonalne w ściśle określonych okolicznościach.

Poniższe przypadki należą do łatwych:

• rekurencja ogona
• bezpośrednia rekurencja liniowa

Oprócz jawnego stosu, innym schematem przekształcania rekurencji w iterację jest użycie trampoliny.

W tym przypadku funkcje zwracają wynik końcowy lub zamykają wywołanie funkcji, które w innym przypadku wykonałby. Następnie funkcja inicjująca (trampolinowanie) powołuje się na zamknięte zamknięcia, aż do osiągnięcia końcowego wyniku.

To podejście działa w przypadku funkcji wzajemnie rekurencyjnych, ale obawiam się, że działa tylko w przypadku wezwań ogonowych.

http://en.wikipedia.org/wiki/Trampoline_(computers)

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

Przejrzyj następujące wpisy na wikipedii, możesz je wykorzystać jako punkt wyjścia do znalezienia pełnej odpowiedzi na swoje pytanie.

• Rekurencja w informatyce
• Relacja powtarzalności

Zawiera akapit, który może dać ci wskazówkę, od czego zacząć:

Rozwiązanie relacji rekurencyjnej oznacza uzyskanie rozwiązania w formie zamkniętej : nierekurencyjnej funkcji n.

Zobacz także ostatni akapit tego wpisu .

Możliwe jest przekonwertowanie dowolnego algorytmu rekurencyjnego na nierekurencyjny, ale często logika jest znacznie bardziej złożona i wymaga to użycia stosu. W rzeczywistości sama rekursja używa stosu: stosu funkcji.

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

tazzego, rekurencja oznacza, że ​​funkcja zadzwoni sama, czy ci się to podoba, czy nie. Kiedy ludzie mówią o tym, czy rzeczy można zrobić bez rekurencji, mają na myśli to i nie można powiedzieć „nie, to nieprawda, ponieważ nie zgadzam się z definicją rekurencji” jako prawidłowego stwierdzenia.

Mając to na uwadze, prawie wszystko, co mówisz, to bzdury. Jedyną inną rzeczą, o której mówisz, że to nie nonsens, jest pomysł, że nie możesz sobie wyobrazić programowania bez stosu wywołań. Jest to coś, co robiono przez dziesięciolecia, dopóki popularność nie zaczęła się używać callstack. Starym wersjom FORTRAN brakowało callstacka i działały dobrze.

Nawiasem mówiąc, istnieją języki kompletne Turinga, które implementują tylko rekurencję (np. SML) jako sposób zapętlenia. Istnieją również języki kompletne Turinga, które implementują tylko iterację jako sposób zapętlenia (np. FORTRAN IV). Teza Kościoła-Turinga dowodzi, że wszystko, co możliwe w językach tylko rekurencyjnych, można zrobić w języku nierekurencyjnym i odwrotnie, ponieważ oba mają właściwość kompletności Turinga.

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