Czy rekursja jest funkcją samą w sobie?

... czy to tylko praktyka?

Pytam o to z powodu kłótni z moim profesorem: straciłem uznanie za wywołanie funkcji rekurencyjnie na podstawie tego, że nie uwzględniliśmy rekurencji w klasie, a moim argumentem jest to, że nauczyliśmy się tego niejawnie poprzez naukę returni metody.

Pytam, bo podejrzewam, że ktoś ma ostateczną odpowiedź.

Na przykład, jaka jest różnica między następującymi dwiema metodami:

public static void a() {
    return a();
    }

public static void b() {
    return a();
    }

Oprócz „ aciągłego na zawsze” (w rzeczywistym programie jest on używany poprawnie do ponownego monitowania użytkownika w przypadku podania nieprawidłowych danych wejściowych), czy istnieje jakaś podstawowa różnica między ai b? W jaki sposób są one traktowane inaczej w przypadku niezoptymalizowanego kompilatora?

Ostatecznie wszystko sprowadza się do tego, czy ucząc się return a()z btego, nauczyliśmy się również return a()z tego a. Czy my?

Odpowiadając na Twoje konkretne pytanie: Nie, z punktu widzenia nauki języka rekurencja nie jest funkcją. Jeśli twój profesor naprawdę wystawił ci punkty za używanie „funkcji”, której jeszcze nie nauczał, to było źle.

Czytając między wierszami, jedną z możliwości jest to, że używając rekursji, uniknąłeś kiedykolwiek funkcji, która miała być efektem uczenia się jego kursu. Na przykład, być może w ogóle nie używałeś iteracji, a może użyłeś tylko forpętli, zamiast używać obu foriwhile . Często zdarza się, że zadanie ma na celu sprawdzenie twoich zdolności do robienia pewnych rzeczy, a jeśli tego nie zrobisz, twój profesor po prostu nie może przyznać ci ocen zarezerwowanych dla tej funkcji. Jeśli jednak to rzeczywiście była przyczyna twojej utraty ocen, profesor powinien potraktować to jako własne doświadczenie edukacyjne - jeśli zademonstrowanie pewnych efektów uczenia się jest jednym z kryteriów przydziału, należy to jasno wyjaśnić studentom .

Powiedziawszy to, zgadzam się z większością innych komentarzy i odpowiedzi, że iteracja jest lepszym wyborem niż rekurencja tutaj. Jest kilka powodów i chociaż inni ludzie do pewnego stopnia ich dotykali, nie jestem pewien, czy w pełni wyjaśnili myśl, która za nimi stoi.

Przepełnienia stosu

Bardziej oczywistym jest to, że ryzykujesz popełnienie błędu przepełnienia stosu. Realistycznie rzecz biorąc, metoda, którą napisałeś, jest bardzo mało prawdopodobne, aby faktycznie doprowadziła do takiej sytuacji, ponieważ użytkownik musiałby wiele razy podawać nieprawidłowe dane, aby faktycznie wywołać przepełnienie stosu.

Należy jednak pamiętać o tym, że na stosie będą znajdować się nie tylko sama metoda, ale także inne metody wyżej lub niżej w łańcuchu wywołań. Z tego powodu przypadkowe pochłanianie dostępnego miejsca na stosie jest dość niegrzeczne dla każdej metody. Nikt nie chce ciągle martwić się o wolne miejsce na stosie, gdy piszą kod, ze względu na ryzyko, że inny kod może niepotrzebnie go wykorzystać dużo.

Jest to część bardziej ogólnej zasady w projektowaniu oprogramowania zwanej abstrakcją. Zasadniczo, kiedy dzwonisz DoThing(), wszystko, o co powinieneś się troszczyć, to to, że rzecz jest załatwiona. Nie powinieneś martwić się szczegółami implementacji, jak to się robi. Ale chciwe użycie stosu łamie tę zasadę, ponieważ każdy bit kodu musi martwić się o to, ile stosu może bezpiecznie założyć, że został mu pozostawiony przez kod w innym miejscu łańcucha wywołań.

Czytelność

Drugim powodem jest czytelność. Ideałem, do którego powinien aspirować kod, jest dokument czytelny dla człowieka, w którym każda linia opisuje po prostu, co robi. Weź te dwa podejścia:

private int getInput() {
    int input;
    do {
        input = promptForInput();
    } while (!inputIsValid(input))
    return input;
}

przeciw

private int getInput() {
    int input = promptForInput();
    if(inputIsValid(input)) {
        return input;
    }
    return getInput();
}

Tak, oba działają i tak, oba są dość łatwe do zrozumienia. Ale jak te dwa podejścia można opisać po angielsku? Myślę, że byłoby to coś takiego:

Będę prosił o wprowadzenie danych, dopóki dane wejściowe nie będą prawidłowe, a następnie zwrócę je

przeciw

Poproszę o wprowadzenie danych, a jeśli dane wejściowe są prawidłowe, zwrócę je, w przeciwnym razie otrzymam dane wejściowe i zamiast tego zwrócę wynik

Być może możesz wymyślić nieco mniej niezgrabne sformułowanie tego drugiego, ale myślę, że zawsze okaże się, że pierwszy z nich będzie dokładniejszym, koncepcyjnie, opisem tego, co faktycznie próbujesz zrobić. Nie oznacza to, że rekurencja jest zawsze mniej czytelna. W sytuacjach, w których świeci, takich jak przechodzenie po drzewie, możesz przeprowadzić ten sam rodzaj analizy obok siebie między rekurencją a innym podejściem i prawie na pewno zauważysz, że rekursja daje kod, który jest wyraźniej samoopisujący się, wiersz po wierszu.

W oderwaniu oba te elementy są małymi punktami. Jest bardzo mało prawdopodobne, że kiedykolwiek doprowadziłoby to do przepełnienia stosu, a wzrost czytelności jest niewielki. Ale każdy program będzie zbiorem wielu z tych małych decyzji, więc nawet jeśli w izolacji nie mają one większego znaczenia, ważne jest, aby poznać zasady stojące za ich prawidłowym wykonaniem.

Odpowiadając na pytanie dosłowne, a nie na metapytanie: rekurencja jest cechą w tym sensie, że nie wszystkie kompilatory i / lub języki koniecznie na to pozwalają. W praktyce jest to oczekiwane od wszystkich (zwykłych) nowoczesnych kompilatorów - iz pewnością wszystkich kompilatorów Javy! - ale nie jest to uniwersalna prawda.

Jako wymyślony przykład tego, dlaczego rekursja może nie być obsługiwana, rozważmy kompilator, który przechowuje adres zwrotny funkcji w statycznej lokalizacji; może tak być na przykład w przypadku kompilatora mikroprocesora, który nie ma stosu.

Dla takiego kompilatora, kiedy wywołujesz taką funkcję

a();

jest zaimplementowany jako

move the address of label 1 to variable return_from_a
jump to label function_a
label 1

i definicja a (),

function a()
{
   var1 = 5;
   return;
}

jest zaimplementowany jako

label function_a
move 5 to variable var1
jump to the address stored in variable return_from_a

Miejmy nadzieję, że problem podczas próby wywołania a()rekurencyjnego w takim kompilatorze jest oczywisty; kompilator nie wie już, jak powrócić z wywołania zewnętrznego, ponieważ adres zwrotny został nadpisany.

W przypadku kompilatora, którego faktycznie używałem (myślę, że późne lata 70. lub wczesne 80. XX wieku) bez obsługi rekurencji problem był nieco bardziej subtelny: adres zwrotny byłby przechowywany na stosie, tak jak we współczesnych kompilatorach, ale zmienne lokalne nie były 't. (Teoretycznie powinno to oznaczać, że rekurencja była możliwa dla funkcji bez niestatycznych zmiennych lokalnych, ale nie pamiętam, czy kompilator jawnie to obsługiwał, czy nie. Z jakiegoś powodu mógł potrzebować niejawnych zmiennych lokalnych).

Patrząc w przyszłość, mogę sobie wyobrazić wyspecjalizowane scenariusze - być może bardzo równoległe systemy - w których brak konieczności zapewniania stosu dla każdego wątku może być korzystny, a zatem rekursja jest dozwolona tylko wtedy, gdy kompilator może zrefaktoryzować ją w pętlę. (Oczywiście prymitywne kompilatory, które omówiłem powyżej, nie były w stanie wykonać skomplikowanych zadań, takich jak refaktoryzacja kodu.)

Nauczyciel chce wiedzieć, czy studiowałeś, czy nie. Najwyraźniej nie rozwiązałeś problemu w sposób, w jaki cię nauczył ( dobra droga ; iteracja), a zatem uważa, że ​​nie. Jestem za kreatywnymi rozwiązaniami, ale w tym przypadku muszę zgodzić się z twoim nauczycielem z innego powodu:
jeśli użytkownik zbyt wiele razy wprowadzi nieprawidłowe dane (np. Przytrzymując wciśnięty klawisz Enter), będziesz mieć wyjątek przepełnienia stosu i rozwiązanie ulegnie awarii. Ponadto rozwiązanie iteracyjne jest wydajniejsze i łatwiejsze w utrzymaniu. Myślę, że to jest powód, dla którego twój nauczyciel powinien był ci podać.

Odejmowanie punktów, ponieważ „nie uwzględniliśmy rekursji w klasie” jest okropne. Jeśli nauczyłeś się, jak wywołać funkcję A, która wywołuje funkcję B, która wywołuje funkcję C, która wraca do B, która wraca do A, która wraca do dzwoniącego, a nauczyciel nie powiedział ci wyraźnie, że muszą to być różne funkcje (które miałoby miejsce na przykład w starych wersjach FORTRAN), nie ma powodu, aby A, B i C nie mogły być tą samą funkcją.

Z drugiej strony musielibyśmy zobaczyć rzeczywisty kod, aby zdecydować, czy w twoim konkretnym przypadku użycie rekursji jest naprawdę właściwe. Nie ma wielu szczegółów, ale brzmi źle.

Jest wiele punktów widzenia, na które warto zwrócić uwagę w odniesieniu do konkretnego pytania, które zadałeś, ale mogę powiedzieć, że z punktu widzenia nauki języka rekurencja nie jest funkcją samą w sobie. Jeśli twój profesor naprawdę zadokował ci oceny za używanie „funkcji”, której jeszcze nie uczył, to było błędne, ale jak powiedziałem, są tu inne punkty widzenia, które należy wziąć pod uwagę, które faktycznie sprawiają, że profesor ma rację przy odejmowaniu punktów.

Z tego, co mogę wywnioskować z twojego pytania, używanie funkcji rekurencyjnej do pytania o dane wejściowe w przypadku niepowodzenia danych wejściowych nie jest dobrą praktyką, ponieważ każde wywołanie funkcji rekurencyjnej jest wypychane na stos. Ponieważ ta rekurencja jest sterowana przez dane wejściowe użytkownika, możliwe jest posiadanie nieskończonej funkcji rekurencyjnej, co skutkuje StackOverflow.

Nie ma różnicy między tymi 2 przykładami, które wspomniałeś w swoim pytaniu, w sensie tego, co robią (ale różnią się w inny sposób) - W obu przypadkach adres zwrotny i wszystkie informacje o metodzie są ładowane na stos. W przypadku rekurencji adres zwrotny jest po prostu linią bezpośrednio po wywołaniu metody (oczywiście nie jest to dokładnie to, co widzisz w samym kodzie, ale raczej w kodzie utworzonym przez kompilator). W Javie, C i Pythonie rekurencja jest dość kosztowna w porównaniu z iteracją (ogólnie), ponieważ wymaga alokacji nowej ramki stosu. Nie wspominając o tym, że możesz uzyskać wyjątek przepełnienia stosu, jeśli dane wejściowe nie są poprawne zbyt wiele razy.

Wydaje mi się, że profesor odliczył punkty, ponieważ rekursja jest uważana za osobny temat i jest mało prawdopodobne, aby ktoś bez doświadczenia w programowaniu pomyślał o rekurencji. (Oczywiście nie oznacza to, że nie, ale jest to mało prawdopodobne).

IMHO, myślę, że profesor ma rację, odejmując Ci punkty. Mogłeś łatwo przenieść część walidacyjną do innej metody i użyć jej w następujący sposób:

public bool foo() 
{
  validInput = GetInput();
  while(!validInput)
  {
    MessageBox.Show("Wrong Input, please try again!");
    validInput = GetInput();
  }
  return hasWon(x, y, piece);
}

Jeśli to, co zrobiłeś, rzeczywiście można rozwiązać w ten sposób, to to, co zrobiłeś, było złą praktyką i powinno się tego unikać.

Może twój profesor jeszcze tego nie nauczył, ale wygląda na to, że jesteś gotowy, aby poznać zalety i wady rekurencji.

Główną zaletą rekurencji jest to, że algorytmy rekurencyjne są często znacznie łatwiejsze i szybsze do napisania.

Główną wadą rekurencji jest to, że algorytmy rekurencyjne mogą powodować przepełnienie stosu, ponieważ każdy poziom rekurencji wymaga dodania do stosu dodatkowej ramki stosu.

W przypadku kodu produkcyjnego, w którym skalowanie może skutkować znacznie większą liczbą poziomów rekursji w produkcji niż w testach jednostkowych programisty, wada zwykle przeważa nad zaletą, a kod rekurencyjny jest często unikany, gdy jest to praktyczne.

Jeśli chodzi o konkretne pytanie, czy rekurencja jest funkcją, jestem skłonny powiedzieć, że tak, ale po ponownej interpretacji pytania. Istnieją wspólne projekty języków i kompilatorów, które umożliwiają rekurencję, a języki kompletne według Turinga w ogóle nie pozwalają na rekursję . Innymi słowy, rekurencja to zdolność, która jest włączana przez pewne wybory w projekcie języka / kompilatora.

• Obsługa funkcji pierwszej klasy umożliwia rekurencję przy bardzo minimalnych założeniach; zobacz na przykład pisanie pętli w Unlambda lub to rozwlekłe wyrażenie Pythona, które nie zawiera odwołań do samych siebie, pętli ani przypisań:

  >>> map((lambda x: lambda f: x(lambda g: f(lambda v: g(g)(v))))(
  ...   lambda c: c(c))(lambda R: lambda n: 1 if n < 2 else n * R(n - 1)),
  ...   xrange(10))
  [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
  

• Języki / kompilatory, które używają późnego wiązania lub które definiują deklaracje do przodu , umożliwiają rekurencję. Na przykład, podczas gdy Python zezwala na poniższy kod, jest to wybór projektu (późne wiązanie), a nie wymaganie dla systemu kompletnego Turing . Wzajemnie rekurencyjne funkcje często zależą od obsługi deklaracji forward.

  factorial = lambda n: 1 if n < 2 else n * factorial(n-1)
  

• Języki z typami statycznymi, które pozwalają na rekurencyjnie zdefiniowane typy, przyczyniają się do włączenia rekursji. Zobacz implementację Y Combinator w Go . Bez rekurencyjnie zdefiniowanych typów nadal byłoby możliwe użycie rekurencji w Go, ale uważam, że konkretnie kombinator Y byłby niemożliwy.

Z tego, co mogę wywnioskować z twojego pytania, używanie funkcji rekurencyjnej do pytania o dane wejściowe w przypadku niepowodzenia danych wejściowych nie jest dobrą praktyką. Czemu?

Ponieważ każde wywołanie funkcji rekurencyjnych jest wypychane na stos. Ponieważ ta rekurencja jest sterowana przez dane wejściowe użytkownika, możliwe jest posiadanie nieskończonej funkcji rekurencyjnej, co skutkuje StackOverflow :-p

Mając do tego nierekurencyjną pętlę, należy to zrobić.

Rekurencja to koncepcja programowania , funkcja (podobnie jak iteracja) i praktyka . Jak widać z linku, istnieje duża dziedzina badań poświęconych temu tematowi. Być może nie musimy zagłębiać się w ten temat, aby zrozumieć te punkty.

Rekursja jako funkcja

Mówiąc najprościej, Java obsługuje to niejawnie, ponieważ pozwala metodzie (która jest w zasadzie funkcją specjalną) mieć „wiedzę” o sobie i innych metodach tworzących klasę, do której należy. Rozważ język, w którym tak nie jest: byłbyś w stanie napisać treść tej metody a, ale nie byłbyś w stanie zawrzeć w niej wywołania a. Jedynym rozwiązaniem byłoby użycie iteracji w celu uzyskania tego samego wyniku. W takim języku należałoby dokonać rozróżnienia między funkcjami świadomymi swojego istnienia (przy użyciu określonego tokena składni), a tymi, które tego nie robią! Właściwie cała grupa języków robią to rozróżnienie (patrz Lisp i ML na przykład rodziny ). Co ciekawe, Perl umożliwia nawet funkcje anonimowe (tzwlambdy ), aby połączyć się rekurencyjnie (ponownie, z dedykowanym składni).

brak rekursji?

W przypadku języków, które nawet nie obsługują możliwości rekurencji, często istnieje inne rozwiązanie w postaci kombinatora stałoprzecinkowego , ale nadal wymaga on obsługi funkcji jako tak zwanych obiektów pierwszej klasy (tj. Obiektów, które mogą być manipulowane w samym języku).

Rekursja jako praktyka

Posiadanie tej funkcji w języku nie oznacza, że ​​jest to idiomatyczne. W Javie 8 uwzględniono wyrażenia lambda, więc przyjęcie funkcjonalnego podejścia do programowania może stać się łatwiejsze. Istnieją jednak praktyczne kwestie:

• składnia nadal nie jest zbyt przyjazna dla rekurencji
• kompilatory mogą nie być w stanie wykryć tej praktyki i jej zoptymalizować

Podsumowując

Na szczęście (lub dokładniej, ze względu na łatwość użycia) Java domyślnie pozwala metodom być świadomymi siebie samych, a tym samym obsługuje rekursję, więc nie jest to tak naprawdę problem praktyczny, ale nadal pozostaje problemem teoretycznym i przypuszczam, że Twój nauczyciel chciał się tym zająć konkretnie. Poza tym, w świetle niedawnej ewolucji języka, może się on w przyszłości przekształcić w coś ważnego.