Czy jest coś, co można zrobić za pomocą rekurencji, czego nie można zrobić za pomocą pętli?

126

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?

Pikamander2
źródło
13
Poważnie w to wątpię. Rekurencja jest uwielbioną pętlą.
Wyścigi lekkości na orbicie
6
Widząc rozbieżne kierunki, w które idą odpowiedzi (i po prostu nie udało mi się zapewnić lepszego), możesz zrobić ktoś, kto spróbuje odpowiedzieć na przysługę, jeśli podasz nieco więcej tła i jakiego rodzaju odpowiedzi szukasz. Czy chcesz teoretyczny dowód na hipotetyczne maszyny (z nieograniczonym czasem przechowywania i czasem pracy)? Lub praktyczne przykłady? (Gdzie „byłoby absurdalnie skomplikowane” można by zakwalifikować jako „nie da się tego zrobić”.) Czy coś innego?
5gon12eder
8
@LightnessRacesinOrbit Do mojego ucha, który nie mówi po angielsku, „Recursion to gloryfikowana pętla” brzmi, co masz na myśli „Równie dobrze możesz użyć konstrukcji pętli zamiast rekurencyjnego połączenia, a koncepcja nie zasługuje na swoją własną nazwę” . Być może zatem źle interpretuję idiom „gloryfikowany”.
hyde
13
Co z funkcją Ackermanna? en.wikipedia.org/wiki/Ackermann_function , niezbyt przydatne, ale niemożliwe do zrobienia przez zapętlenie. (Możesz również sprawdzić ten film youtube.com/watch?v=i7sm9dzFtEI od Computerphile)
WizardOfMenlo
8
@WizardOfMenlo kod befunge jest implementacją rozwiązania ERRE (które jest również rozwiązaniem interaktywnym ... ze stosem). Podejście iteracyjne ze stosem może naśladować wywołanie rekurencyjne. W każdym programowaniu, które jest odpowiednio potężne, jedna konstrukcja pętli może być wykorzystana do emulacji innego. Maszyna rejestr z instrukcją 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:

164

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.

Scant Roger
źródło
120
Zasadniczo wykonywanie pętli zamiast rekurencji oznacza ręczne obsługiwanie stosu.
Silviu Burcea
15
... stos (y) . Następująca sytuacja może zdecydowanie preferować posiadanie więcej niż jednego stosu. Rozważ jedną funkcję rekurencyjną, Aktóra znajduje coś w drzewie. Za każdym razem, gdy Anapotyka tę rzecz, uruchamia inną funkcję rekurencyjną, Bktóra znajduje pokrewną rzecz w poddrzewie w miejscu, w którym została uruchomiona A. Po Bzakończeniu rekurencji wraca do niej A, a ta kontynuuje swoją własną rekurencję. Można zadeklarować jeden stos dla Ai jeden dla Blub umieścić Bstos w Apętli. Jeśli ktoś nalega na użycie jednego stosu, sprawy stają się naprawdę skomplikowane.
rwong
35
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?
Mason Wheeler,
10
@MasonWheeler 99% czasu „rzeczy” można lepiej zamknąć w operatorze rekurencyjnym, takim jak maplub fold(w rzeczywistości, jeśli zdecydujesz się rozważyć ich prymityw, myślę, że możesz użyć fold/ unfoldjako 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.
Leushenko
7
Możesz porównać dwa ciągi, rekurencyjnie porównując podłańcuchy, ale po prostu porównując każdy znak, jeden po drugim, aż do uzyskania niedopasowania, będzie on działał lepiej i był bardziej czytelny dla czytelnika.
Steven Burnap
78

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:

  • Wszystko, co jest obliczalne, jest obliczalne na maszynie Turinga
  • Każdy język, który może zaimplementować maszynę Turinga (zwany Turing complete), może obliczyć wszystko, co potrafi każdy inny język
  • Ponieważ istnieją maszyny Turinga w językach, w których brak rekurencji (i są inne, które mają rekurencję tylko po przejściu do niektórych innych esolangów), koniecznie jest prawdą, że nic nie można zrobić z rekurencją, czego nie można zrobić z pętla (i nic nie można zrobić z pętlą, której nie można zrobić z rekurencją).

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:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

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.

Społeczność
źródło
29
Kompletność Turinga jest zbyt ważna. Wiele rzeczy jest Turing Complete ( jak Magic the Gathering ), ale to nie znaczy, że jest to to samo, co coś innego, co Turing Complete. Przynajmniej nie na poziomie, który ma znaczenie. Nie chcę chodzić po drzewie z Magic the Gathering.
Scant Roger,
7
Kiedy możesz zredukować problem do „ma on taką samą moc jak maszyna Turinga”, wystarczy go tam dostać. Maszyny Turinga stanowią raczej niewielką przeszkodę, ale to wszystko, czego potrzeba. Nie ma nic, co może zrobić pętla, czego nie może zrobić rekurencja i odwrotnie.
4
Stwierdzenie zawarte w tej odpowiedzi jest oczywiście poprawne, ale odważę się powiedzieć, że argument ten nie jest tak naprawdę przekonujący. Maszyny Turinga nie mają bezpośredniej koncepcji rekurencji, więc powiedzenie „można symulować maszynę Turinga bez rekurencji” tak naprawdę niczego nie dowodzi. Aby udowodnić, że musisz to udowodnić, maszyny Turinga mogą symulować rekurencję. Jeśli tego nie wykażesz, musisz wiernie założyć, że hipoteza Kościoła Turinga dotyczy również rekurencji (co czyni), ale OP zakwestionował to.
5gon12eder
10
Pytanie PO brzmi „może”, a nie „najlepiej”, „najskuteczniej” lub jakiś inny kwalifikator. „Turing Complete” oznacza, że ​​wszystko, co można zrobić za pomocą rekurencji, można również wykonać za pomocą pętli. To, czy jest to najlepszy sposób, aby to zrobić w konkretnej implementacji języka, jest zupełnie inną kwestią.
Steven Burnap
7
„Can” wcale nie jest tym samym, co „best”. Kiedy mylicie „nie najlepiej” z „nie mogę”, zostajecie sparaliżowani, ponieważ bez względu na to, jak coś zrobicie, prawie zawsze jest lepszy sposób.
Steven Burnap
31

Czy istnieją przypadki, w których zadanie można wykonać tylko przy użyciu rekurencji, a nie pętli?

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

hyde
źródło
2
W przypadku zestawu do procesora bez stosu te dwie techniki nagle stają się jedną.
Joshua
@Joshua Rzeczywiście! Jest to kwestia poziomu abstrakcji. Jeśli zejdziesz poziom lub dwa niżej, to tylko bramki logiczne.
hyde
2
To nie do końca prawda. Aby emulować rekurencję z iteracją, potrzebujesz stosu, w którym możliwy jest losowy dostęp. Pojedynczy stos bez losowego dostępu plus skończona ilość bezpośrednio dostępnej pamięci to PDA, który nie jest kompletny w Turingu.
Gilles
@Gilles Stary post, ale dlaczego potrzebny jest stos dostępu losowego? Ponadto, czy wszystkie rzeczywiste komputery nie są nawet mniejsze niż urządzenia PDA, ponieważ mają tylko skończoną ilość bezpośrednio dostępnej pamięci i nie mają żadnego stosu (z wyjątkiem korzystania z tej pamięci)? Nie wydaje się to zbyt praktyczną abstrakcją, jeśli mówi „nie możemy robić rekurencji w rzeczywistości”.
hyde
20

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.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Wykonanie pierwszej iteracyjnej wywołania rekurencyjnego jest łatwe:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Następnie możemy posprzątać, gotoaby odeprzeć welociraptory i cień Dijkstry:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Ale aby usunąć inne wywołania rekurencyjne, będziemy musieli przechowywać wartości niektórych wywołań w stosie:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

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.

Jon Hanna
źródło
Stos stosu połączeń można zastąpić czymś równoważnym tylko wtedy, gdy stos wywołań jest ograniczony lub ktoś ma dostęp do nieograniczonej pamięci poza stosem wywołań. Istnieje znaczna klasa problemów, które można rozwiązać za pomocą automatów push-down, które mają nieograniczony stos wywołań, ale w przeciwnym razie mogą mieć tylko skończoną liczbę stanów.
supercat
To najlepsza odpowiedź, być może jedyna poprawna odpowiedź. Nawet drugi przykład jest wciąż rekurencyjny i na tym poziomie odpowiedź na pierwotne pytanie brzmi „ nie” . Przy szerszej definicji rekurencji nie można uniknąć rekurencji dla funkcji Ackermanna.
gerrit
@gerrit, a przy węższym zakresie, pozwala tego uniknąć. Ostatecznie sprowadza się to do krawędzi tego, co robimy lub nie stosujemy tej przydatnej etykiety, której używamy dla określonego kodu.
Jon Hanna
1
Dołączył do strony, aby zagłosować. Funkcja Ackermann / ma / ma charakter rekurencyjny. Wdrożenie struktury rekurencyjnej za pomocą pętli i stosu nie czyni z niej iteracyjnego rozwiązania, właśnie przeniosłeś rekurencję do przestrzeni użytkownika.
Aaron McMillin
9

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:

  • Odpowiedź brzmi „nie”, jeśli możesz mieć dodatkowy stos podczas zapętlania.
  • Odpowiedź brzmi „tak”, jeśli nie ma żadnych dodatkowych danych podczas zapętlania.

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ć forpętlę, która przechodzi przez każdy z Nsegmentów, wywołuje mergesortje 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 forpę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.

Mehrdad
źródło
Co więcej, należy wziąć pod uwagę, że zestaw problemów, które można rozwiązać za pomocą automatu przesuwającego, jest większy niż zestaw, który można rozwiązać za pomocą automatu skończonego (deterministycznego lub nie), ale mniejszy niż zbiór, który można rozwiązać za pomocą Maszyna Turinga.
supercat
8

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:

  • Przypadek rekurencji = przepływ kontrolny + stos (+ sterty)
  • Przypadek pętli = Kontrola przepływu + Sterta

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

  1. Bez stosu, bez stosu: rekurencja i struktury dynamiczne są niemożliwe. (rekurencja = pętla)
  2. Stack, no heap: rekurencja jest OK, struktury dynamiczne są niemożliwe. (rekurencja> pętla)
  3. Brak stosu, stosu: rekurencja jest niemożliwa, struktury dynamiczne są OK. (rekurencja = pętla)
  4. Stos, stos: rekurencja i struktury dynamiczne są OK. (rekurencja = pętla)

Jeśli reguły gry są nieco bardziej rygorystyczne, a implementacja rekurencyjna jest niedozwolona w celu użycia pętli, otrzymujemy to:

  1. Bez stosu, bez stosu: rekurencja i struktury dynamiczne są niemożliwe. (rekurencja <pętla)
  2. Stack, no heap: rekurencja jest OK, struktury dynamiczne są niemożliwe. (rekurencja> pętla)
  3. Brak stosu, stosu: rekurencja jest niemożliwa, struktury dynamiczne są OK. (rekurencja <pętla)
  4. Stos, stos: rekurencja i struktury dynamiczne są OK. (rekurencja = pętla)

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.

Alexander Kogtenkov
źródło
2

Tak. Istnieje kilka typowych zadań, które są łatwe do wykonania przy użyciu rekurencji, ale niemożliwe za pomocą samych pętli:

  • Powoduje przepełnienie stosu.
  • Całkowicie zagmatwane początkujące programiści.
  • Tworzenie szybko wyglądających funkcji, które w rzeczywistości są O (n ^ n).
jpa
źródło
3
Proszę, te pętle są naprawdę łatwe, cały czas je widzę. Do licha, przy odrobinie wysiłku nawet nie potrzebujesz pętli. Nawet jeśli rekursja jest łatwiejsza.
AviD
1
właściwie A (0, n) = n + 1; A (m, 0) = A (m-1,1), jeśli m> 0; A (m, n) = A (m-1, A (m, n-1)), jeśli m> 0, n> 0 rośnie nawet nieco szybciej niż O (n ^ n) (dla m = n) :)
John Donn
1
@JohnDonn Więcej niż trochę, to super wykładniczy. dla n = 3 n ^ n ^ n dla n = 4 n ^ n ^ n ^ n ^ n i tak dalej. n do potęgi n razy.
Aaron McMillin
1

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.

gnasher729
źródło
3
Nie jestem pewien, jak to się odnosi do powyższego pytania? Czy możesz wyjaśnić to połączenie?
Yakk
1
Zastąpienie nieprecyzyjnej „pętli” istotnym rozróżnieniem między „pętlą z ograniczoną liczbą iteracji” i „pętlą z nieograniczoną liczbą iteracji”, co, jak sądzę, wszyscy znają z CS 101.
gnasher729,
jasne, ale nadal nie dotyczy to pytania. Pytanie dotyczy pętli i rekurencji, a nie prymitywnej rekurencji i rekurencji. Wyobraź sobie, że ktoś zapytał o różnice w C / C ++, a ty odpowiedziałeś o różnicy między K&R C a Ansi C. Jasne, że to czyni wszystko bardziej precyzyjnym, ale nie odpowiada na pytanie.
Jak
1

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.

BЈовић
źródło
0
  • Jeśli wywołanie rekurencyjne jest pierwszą lub ostatnią instrukcją (wyłączając sprawdzanie warunków) funkcji rekurencyjnej, dość łatwo jest przetłumaczyć ją na strukturę zapętloną.
  • Ale jeśli funkcja zrobi kilka innych rzeczy przed i po wywołaniu rekurencyjnym , wówczas przekształcenie jej w pętle byłoby kłopotliwe.
  • Jeśli funkcja ma wiele wywołań rekurencyjnych, przekształcenie jej w kod wykorzystujący tylko pętle będzie prawie niemożliwe. Potrzebny będzie pewien stos, aby nadążyć za danymi. W rekursji sam stos wywołań będzie działał jak stos danych.
Gulszan
źródło
Chodzenie po drzewie ma wiele wywołań rekurencyjnych (po jednym dla każdego dziecka), ale w prosty sposób przekształca się w pętlę przy użyciu jawnego stosu. Z drugiej strony parsery są często irytujące w transformacji.
CodesInChaos
@CodesInChaos Edited.
Gulshan
-6

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.

Ben1980
źródło
2
Naiwna rekurencyjna implementacja liczb Fibonacciego z rekurencją skończy się „przed czasem”, zanim zabraknie miejsca na stosie. Sądzę, że istnieją inne problemy, które są lepsze dla tego przykładu. Ponadto w przypadku wielu problemów wersja pętli ma taki sam wpływ na pamięć jak rekurencyjna, tylko na stosie zamiast na stosie (jeśli język programowania je rozróżnia).
Paŭlo Ebermann
6
Pętla może być również „bardzo niebezpieczna”, jeśli zapomnisz o zwiększeniu zmiennej pętli ...
h22
2
Rzeczywiście, celowe tworzenie przepełnienia stosu jest zadaniem, które staje się bardzo trudne bez użycia rekurencji.
5gon12eder
@ 5gon12eder, który prowadzi nas do Jakie metody są dostępne, aby uniknąć przepełnienia stosu w algorytmie rekurencyjnym? - przydatne może być pisanie w celu włączenia TCO lub Memoisation. Podejścia iteracyjne vs. rekurencyjne są również interesujące, ponieważ dotyczą dwóch różnych metod rekurencyjnych dla Fibonacciego.
1
Przez większość czasu, jeśli dostaniesz przepełnienie stosu podczas rekurencji, miałbyś zawieszoną wersję iteracyjną. Przynajmniej te pierwsze rzucają śladem stosu.
Jon Hanna