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

181

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))
Tordek
źródło
3
Nie rozumiem, jak to jest kontrprzykład. Technika stosu będzie działać. To nie będzie ładne i nie zamierzam tego pisać, ale jest wykonalne. Wygląda na to, że akdas potwierdza to w twoim linku.
Matthew Flaschen
Twój (num-sposoby xy) to po prostu (x + y) choosex = (x + y)! / (X! Y!), Który nie wymaga rekurencji.
ShreevatsaR
3
Duplikat: stackoverflow.com/questions/531668
Henk Holterman
Powiedziałbym, że rekurencja jest jedynie wygodą.
e2-e4

Odpowiedzi:

181

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.

Ian
źródło
10
Czy Church-Turing nie został jeszcze udowodniony?
Liran Orevi
15
@eyelidlessness: Jeśli możesz zaimplementować A w B, oznacza to, że B ma co najmniej tyle mocy, co A. Jeśli nie możesz wykonać instrukcji A w implementacji A-B, to nie jest to implementacja. Jeśli A można zaimplementować w B, a B można zaimplementować w A, moc (A)> = moc (B), a moc (B)> = moc (A). Jedynym rozwiązaniem jest moc (A) == moc (B).
Tordek
6
do: akapit pierwszy: Mówisz o równoważności modeli obliczeniowych, a nie o tezie Churcha-Turinga. Równoważność została potwierdzona przez AFAIR przez Churcha i / lub Turinga, ale nie jest to teza. Teza ta jest eksperymentalnym faktem, że wszystko, co intuicyjnie obliczalne, jest obliczalne w ścisłym sensie matematycznym (za pomocą maszyn Turinga / funkcji rekurencyjnych itp.). Można by to obalić, gdyby stosując prawa fizyki moglibyśmy zbudować niektóre nieklasyczne komputery obliczające coś, czego maszyny Turinga nie są w stanie zrobić (np. Problem zatrzymania). Natomiast równoważność jest twierdzeniem matematycznym i nie zostanie obalona.
sdcvvc
7
Jak do cholery ta odpowiedź uzyskała jakieś pozytywne głosy? Najpierw miesza kompletność Turinga z tezą Kościoła-Turinga, a następnie robi kilka niepoprawnych falowania rąk, wspominając o „zaawansowanych” systemach i upuszczając leniwą nieskończoną rekurencję ogona (co można zrobić w C lub dowolnym pełnym języku Turinga, ponieważ… eee. Czy ktoś wie, co znaczy Turing Complete?). A zatem pełen nadziei wniosek, jak gdyby to było pytanie do Oprah, a wszystko, czego potrzebujesz, to być pozytywnym i podnoszącym na duchu? Okropna odpowiedź!
ex0du5
8
A bs o semantyce ??? Naprawdę? To jest pytanie o transformacje składniowe i jakimś cudem stało się świetnym sposobem na nazwanie Dijkstry i sugerowanie, że wiesz coś o rachunku pi? Wyjaśnię to jasno: to, czy spojrzy się na semantykę denotacyjną języka czy innego modelu, nie będzie miało wpływu na odpowiedź na to pytanie. To, czy językiem jest asembler czy język generatywnego modelowania domen, nic nie znaczy. Chodzi tylko o kompletność Turinga i przekształcenie „zmiennych stosu” w „stos zmiennych”.
ex0du5
43

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

Konrad Rudolph
źródło
Świetna odpowiedź! Jednak w praktyce mam duże trudności z przekształceniem rekurencyjnych alg w iteracyjne. Na przykład do tej pory nie byłem w stanie przekształcić monomorficznego typera przedstawionego tutaj community.topcoder.com/... w algorytm iteracyjny
Nils
31

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.

Vinko Vrsalovic
źródło
13

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.

jerryjvl
źródło
9
  • 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.
Khaled.K
źródło
7

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

dfa
źródło
17
Nie powiedziałbym, że zawsze przyjemniej jest czytać. Zarówno iteracja, jak i rekurencja mają swoje miejsce.
Matthew Flaschen
6

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

Heinzi
źródło
Który z nich niweczy cel, jeśli twoja struktura danych stosu jest przydzielona na stosie, lub zajmuje dużo więcej czasu, jeśli jest przydzielona na stosie, nie? Brzmi dla mnie banalnie, ale nieefektywnie.
conradkleinespel
1
@conradk W niektórych przypadkach praktyczną rzeczą jest zrobić, jeśli trzeba wykonać operację rekurencyjną dla drzewa na problemie, który jest wystarczająco duży, aby wyczerpać stos wywołań; pamięć sterty jest zwykle o wiele bogatsza.
jamesdlin
4

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

Zayenz
źródło
2

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

JOBBINE
źródło
1

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.

Matthias Wandel
źródło
0

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

Poniższe przypadki należą do łatwych:

Nick Dandoulakis
źródło
0

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)

Chris Vest
źródło
0

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

sfussenegger
źródło
1
Myślę, że OP szuka dowodu lub czegoś innego
Tim
0

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

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 .

Alberto Zaccagni
źródło
-1

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.

Richard
źródło
-3

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
Jules
źródło