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

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?

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.

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.

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

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.

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.

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.

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

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.

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.

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

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.