Są chwile, w których użycie rekurencji jest lepsze niż użycie pętli, i czasy, w których użycie pętli jest lepsze niż użycie rekurencji. Wybór „właściwego” pozwala zaoszczędzić zasoby i / lub spowodować zmniejszenie liczby wierszy kodu.
Czy istnieją przypadki, w których zadanie można wykonać tylko przy użyciu rekurencji, a nie pętli?
INC (r)
,JZDEC (r, z)
może wprowadzić maszynę Turinga. Nie ma „rekurencji” - to jest Skok, jeśli Zero inny ZMNIEJSZENIE. Jeśli funkcja Ackermanna jest obliczalna (jest), rejestrująca maszyna może to zrobić.Odpowiedzi:
Tak i nie. Ostatecznie nic nie może obliczyć rekurencji, której nie można zapętlić, ale zapętlenie zajmuje dużo więcej hydrauliki. Dlatego jedyną rzeczą, którą może wykonać rekurencja, której nie można wykonać w pętlach, jest bardzo łatwe wykonanie niektórych zadań.
Idź po drzewie. Chodzenie po drzewie z rekurencją jest głupie-łatwe. To najbardziej naturalna rzecz na świecie. Spacer po drzewie z pętlami jest o wiele mniej prosty. Musisz zachować stos lub inną strukturę danych, aby śledzić to, co zrobiłeś.
Często rekurencyjne rozwiązanie problemu jest ładniejsze. To termin techniczny i ma to znaczenie.
źródło
A
która znajduje coś w drzewie. Za każdym razem, gdyA
napotyka tę rzecz, uruchamia inną funkcję rekurencyjną,B
która znajduje pokrewną rzecz w poddrzewie w miejscu, w którym została uruchomionaA
. PoB
zakończeniu rekurencji wraca do niejA
, a ta kontynuuje swoją własną rekurencję. Można zadeklarować jeden stos dlaA
i jeden dlaB
lub umieścićB
stos wA
pętli. Jeśli ktoś nalega na użycie jednego stosu, sprawy stają się naprawdę skomplikowane.Therefore, the one thing recursion can do that loops can't is make some tasks super easy.
A jedyną rzeczą, którą pętle mogą zrobić, czego rekurencja nie może, jest uczynienie niektórych zadań super łatwymi. Czy widziałeś brzydkie, nieintuicyjne rzeczy, które musisz zrobić, aby przekształcić większość naturalnie iteracyjnych problemów z naiwnej rekurencji w rekurencję ogona, aby nie zniszczyły stosu?map
lubfold
(w rzeczywistości, jeśli zdecydujesz się rozważyć ich prymityw, myślę, że możesz użyćfold
/unfold
jako trzeciej alternatywy dla pętli lub rekurencji). O ile nie piszesz kodu biblioteki, nie ma zbyt wielu przypadków, w których powinieneś martwić się implementacją iteracji, a nie zadaniem, które ma ona wykonać - w praktyce oznacza to, że wyraźne pętle i wyraźna rekurencja są równie słabe abstrakcje, których należy unikać na najwyższym poziomie.Nie.
Przechodząc do samych podstaw niezbędnych minimów w celu obliczenia, wystarczy, aby móc pętli (ta sama w sobie nie jest wystarczający, ale raczej jest niezbędnym elementem). Nie ważne jak .
Każdy język programowania, który może implementować maszynę Turinga, nazywa się Turing complete . Istnieje wiele języków, które są kompletne.
Mój ulubiony język w stylu „to faktycznie działa?” Kompletność Turinga to FRACTRAN , który jest kompletny Turinga . Ma jedną strukturę pętli i można w nim zaimplementować maszynę Turinga. Zatem wszystko, co jest obliczalne, można zaimplementować w języku, który nie ma rekurencji. Dlatego nie ma nic, co rekurencja może dać w zakresie obliczalności, czego nie może zapewnić prosta pętla.
To naprawdę sprowadza się do kilku punktów:
Nie oznacza to, że istnieją pewne klasy problemów, o których łatwiej jest myśleć z rekurencją niż z zapętleniem lub z zapętleniem niż z rekurencją. Jednak te narzędzia są równie potężne.
I chociaż podniosłem to do ekstremum „esolang” (głównie dlatego, że możesz znaleźć rzeczy, które Turing jest kompletne i wdrożone w dość dziwny sposób), nie oznacza to, że esolangi są w jakikolwiek sposób opcjonalne. Istnieje cała lista rzeczy, które przypadkowo zostały ukończone przez Turinga, w tym Magic the Gathering, Sendmail, szablony MediaWiki i system typów Scala. Wiele z nich jest dalekich od optymalnych, jeśli chodzi o robienie czegokolwiek praktycznego, po prostu można obliczyć wszystko, co można obliczyć za pomocą tych narzędzi.
Ta równoważność może stać się szczególnie interesująca, gdy wejdziesz w określony typ rekurencji zwany ogonem .
Jeśli masz, powiedzmy, metodę czynnikową zapisaną jako:
Ten typ rekurencji zostanie przepisany jako pętla - żaden stos nie zostanie użyty. Takie podejścia są rzeczywiście często bardziej eleganckie i łatwiejsze do zrozumienia niż zapisywanie równoważnej pętli, ale znowu, dla każdego wywołania rekurencyjnego może być zapisana równoważna pętla i dla każdej pętli może być napisane wywołanie rekurencyjne.
Istnieje także czas, w którym konwersja z prostą pętlę do połączenia tylnego rekurencyjne połączenia może być zwinięty i bardziej trudny do zrozumienia.
Jeśli chcesz przejść do teorii, zobacz tezę Turinga Kościoła . Można również znaleźć Kościołem Turinga tezę o CS.SE być użyteczne.
źródło
Zawsze możesz przekształcić algorytm rekurencyjny w pętlę, która wykorzystuje strukturę danych Last-First-First-Out (stos AKA) do przechowywania stanu tymczasowego, ponieważ wywołanie rekurencyjne jest dokładnie tym, że przechowywanie bieżącego stanu na stosie, kontynuowanie algorytmu, następnie przywracając stan. Tak krótka odpowiedź brzmi: nie, nie ma takich przypadków .
Można jednak argumentować za „tak”. Weźmy konkretny, prosty przykład: sortowanie po scaleniu. Musisz podzielić dane na dwie części, scalić, posortować części, a następnie połączyć je. Nawet jeśli nie wykonasz rzeczywistego wywołania funkcji języka programowania w celu scalenia sortowania w celu scalenia sortowania na częściach, musisz zaimplementować funkcjonalność identyczną z wykonaniem wywołania funkcji (pchnij stan na własny stos, przejdź do początek pętli z różnymi parametrami początkowymi, a następnie wyskakujący stan ze stosu).
Czy jest to rekurencja, jeśli samodzielnie zaimplementujesz wywołanie rekurencyjne, jako osobne kroki „push push” i „jump to begin” i „pop state”? Odpowiedź na to brzmi: nie, nadal nie nazywa się to rekurencją, nazywa się to iteracją z jawnym stosem (jeśli chcesz użyć ustalonej terminologii).
Uwaga, zależy to również od definicji „zadania”. Jeśli zadaniem jest sortowanie, możesz to zrobić za pomocą wielu algorytmów, z których wiele nie wymaga żadnej rekurencji. Jeśli zadaniem jest zaimplementowanie określonego algorytmu, takiego jak sortowanie po scaleniu, obowiązuje powyższa dwuznaczność.
Zastanówmy się więc, czy istnieją ogólne zadania, dla których istnieją tylko algorytmy przypominające rekurencję. Od komentarza @WizardOfMenlo do pytania, funkcja Ackermanna jest tego prostym przykładem. Tak więc koncepcja rekurencji jest samodzielna, nawet jeśli można ją zaimplementować przy użyciu innej konstrukcji programu komputerowego (iteracja z jawnym stosem).
źródło
Zależy to od tego, jak ściśle zdefiniujesz „rekurencję”.
Jeśli bezwzględnie wymagamy, aby obejmował stos wywołań (lub jakikolwiek inny mechanizm służący do utrzymania stanu programu), zawsze możemy zastąpić go czymś, co nie. Rzeczywiście, języki, które naturalnie prowadzą do intensywnego korzystania z rekurencji, zwykle mają kompilatory, które intensywnie korzystają z optymalizacji wywołania ogona, więc to, co piszesz, jest rekurencyjne, ale to, co uruchamiasz, jest iteracyjne.
Rozważmy jednak przypadek, w którym wykonujemy połączenie rekurencyjne i wykorzystujemy wynik połączenia rekurencyjnego dla tego połączenia rekurencyjnego.
Wykonanie pierwszej iteracyjnej wywołania rekurencyjnego jest łatwe:
Następnie możemy posprzątać,
goto
aby odeprzeć welociraptory i cień Dijkstry:Ale aby usunąć inne wywołania rekurencyjne, będziemy musieli przechowywać wartości niektórych wywołań w stosie:
Teraz, gdy bierzemy pod uwagę kod źródłowy, z pewnością zmieniliśmy naszą metodę rekurencyjną na iteracyjną.
Biorąc pod uwagę, do czego to zostało skompilowane, zmieniliśmy kod, który używa stosu wywołań, aby zaimplementować rekurencję w kodzie, który tego nie robi (i robiąc to, przekształcił kod, który wyrzuci wyjątek przepełnienia stosu nawet dość małych wartości do kodu, który po prostu powrót zajmuje bardzo dużo czasu [patrz Jak mogę zapobiec przepełnieniu stosu przez moją funkcję Ackermana? w celu uzyskania dalszych optymalizacji, które sprawiają, że faktycznie zwraca on wiele innych możliwych danych wejściowych]).
Biorąc pod uwagę ogólną implementację rekurencji, zmieniliśmy kod, który używa stosu wywołań, w kod, który używa innego stosu do przechowywania operacji oczekujących. Moglibyśmy zatem argumentować, że nadal jest rekurencyjny, gdy rozpatrywany jest na tak niskim poziomie.
Na tym poziomie faktycznie nie ma innych sposobów. Więc jeśli uważasz, że ta metoda jest rekurencyjna, to rzeczywiście są rzeczy, bez których nie możemy się obejść. Generalnie jednak nie oznaczamy takiego kodu rekurencyjnym. Termin rekurencja jest użyteczny, ponieważ obejmuje pewien zestaw podejść i umożliwia nam rozmowę o nich, a my nie używamy już żadnego z nich.
Oczywiście wszystko to zakłada, że masz wybór. Istnieją zarówno języki, które zabraniają wywołań rekurencyjnych, jak i języki, w których brakuje struktur zapętlania niezbędnych do iteracji.
źródło
Klasyczna odpowiedź brzmi „nie”, ale pozwól mi wyjaśnić, dlaczego uważam, że „tak” jest lepszą odpowiedzią.
Zanim przejdziemy dalej, usuńmy coś z drogi: z punktu widzenia obliczalności i złożoności:
Okej, teraz postawmy jedną stopę w krainie ćwiczeń, utrzymując drugą stopę w krainie teorii.
Stos wywołań jest strukturą kontrolną , podczas gdy stos ręczny jest strukturą danych . Kontrola i dane nie są jednakowymi pojęciami, ale są równoważne w tym sensie, że można je zredukować do siebie (lub „emulować” przez siebie nawzajem) z punktu widzenia obliczalności lub złożoności.
Kiedy to rozróżnienie może mieć znaczenie? Kiedy pracujesz z prawdziwymi narzędziami. Oto przykład:
Powiedz, że wdrażasz N-way
mergesort
. Możesz miećfor
pętlę, która przechodzi przez każdy zN
segmentów, wywołujemergesort
je osobno, a następnie łączy wyniki.Jak możesz to zrównoleglić z OpenMP?
W sferze rekurencyjnej jest to niezwykle proste: po prostu owiń
#pragma omp parallel for
pętlę od 1 do N i gotowe. W świecie iteracyjnym nie możesz tego zrobić. Musisz odradzać wątki ręcznie i przekazywać im odpowiednie dane ręcznie, aby wiedzieli, co robić.Z drugiej strony istnieją inne narzędzia (takie jak np. Automatyczne wektoryzatory
#pragma vector
), które działają z pętlami, ale są całkowicie bezużyteczne przy rekurencji.Chodzi o to, że tylko dlatego, że możesz udowodnić, że oba paradygmaty są matematycznie równoważne, nie oznacza to, że są one równe w praktyce. Problem, który może być trywialny w automatyzacji w jednym paradygmacie (powiedzmy, równoległości pętli), może być znacznie trudniejszy do rozwiązania w drugim paradygmacie.
tj .: Narzędzia dla jednego paradygmatu nie tłumaczą się automatycznie na inne paradygmaty.
W związku z tym, jeśli potrzebujesz narzędzia do rozwiązania problemu, istnieje prawdopodobieństwo, że narzędzie będzie działać tylko z jednym konkretnym podejściem, aw konsekwencji nie rozwiążesz problemu innym podejściem, nawet jeśli potrafisz matematycznie udowodnić, że problem może być rozwiązany w obu kierunkach.
źródło
Pomijając teoretyczne rozumowanie, przyjrzyjmy się, jak wygląda rekurencja i pętle z punktu widzenia (sprzętowej lub wirtualnej) maszyny. Rekurencja jest kombinacją przepływu sterowania, która pozwala rozpocząć wykonywanie pewnego kodu i powrócić po zakończeniu (w uproszczonym widoku, gdy sygnały i wyjątki są ignorowane) oraz danych, które są przekazywane do tego innego kodu (argumentów) i które są zwracane z to (wynik). Zwykle nie jest zaangażowane jawne zarządzanie pamięcią, jednak domyślnie przydziela się pamięć stosu do zapisywania adresów zwrotnych, argumentów, wyników i pośrednich danych lokalnych.
Pętla jest kombinacją przepływu sterowania i danych lokalnych. Porównując to do rekurencji, widzimy, że ilość danych w tym przypadku jest stała. Jedynym sposobem na przełamanie tego ograniczenia jest użycie pamięci dynamicznej (znanej również jako sterta ), którą można przydzielić (i zwolnić) w razie potrzeby.
Podsumowując:
Zakładając, że część przepływu sterowania jest dość potężna, jedyną różnicą są dostępne typy pamięci. Pozostały nam 4 przypadki (moc wyrażania jest wymieniona w nawiasach):
Jeśli reguły gry są nieco bardziej rygorystyczne, a implementacja rekurencyjna jest niedozwolona w celu użycia pętli, otrzymujemy to:
Zasadniczą różnicą w poprzednim scenariuszu jest to, że brak pamięci stosu nie pozwala rekurencji bez pętli na wykonanie większej liczby kroków podczas wykonywania niż wierszy kodu.
źródło
Tak. Istnieje kilka typowych zadań, które są łatwe do wykonania przy użyciu rekurencji, ale niemożliwe za pomocą samych pętli:
źródło
Istnieje różnica między funkcjami rekurencyjnymi a pierwotnymi funkcjami rekurencyjnymi. Pierwotnymi funkcjami rekurencyjnymi są te, które są obliczane przy użyciu pętli, gdzie maksymalna liczba iteracji każdej pętli jest obliczana przed rozpoczęciem wykonywania pętli. (A „rekurencyjne” tutaj nie ma nic wspólnego z użyciem rekurencji).
Pierwotne funkcje rekurencyjne są zdecydowanie mniej wydajne niż funkcje rekurencyjne. Ten sam wynik uzyskasz, jeśli weźmiesz funkcje korzystające z rekurencji, w których maksymalna głębokość rekurencji musi zostać wcześniej obliczona.
źródło
Jeśli programujesz w c ++ i używasz c ++ 11, musisz wykonać jedną funkcję za pomocą rekurencji: funkcje constexpr. Ale standard ogranicza to do 512, jak wyjaśniono w tej odpowiedzi . Użycie pętli w tym przypadku nie jest możliwe, ponieważ w takim przypadku funkcja nie może być constexpr, ale zmieniono to w c ++ 14.
źródło
źródło
Zgadzam się z pozostałymi pytaniami. Nic nie można zrobić z rekurencją, czego nie można zrobić za pomocą pętli.
ALE moim zdaniem rekursja może być bardzo niebezpieczna. Po pierwsze, niektórym trudniej jest zrozumieć, co faktycznie dzieje się w kodzie. Po drugie, przynajmniej dla C ++ (Java nie jestem pewien) każdy etap rekurencji ma wpływ na pamięć, ponieważ każde wywołanie metody powoduje gromadzenie pamięci i inicjalizację nagłówka metod. W ten sposób możesz wysadzić swój stos. Po prostu spróbuj rekurencji liczb Fibonacciego o wysokiej wartości wejściowej.
źródło