Czy rekursja jest funkcją samą w sobie?


116

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


24
Doskonała debata. Ciekawe, czy wyjaśniłeś to w ten sposób swojemu profesorowi. Jeśli tak, myślę, że powinien dać ci stracony kredyt.
Michael Yaworski

57
Rekursja nie jest nawet pojęciem wyłącznym dla informatyki. Funkcja Fibonacciego, operator silni i wiele innych rzeczy z matematyki (i prawdopodobnie innych dziedzin) są (lub przynajmniej mogą być) wyrażane rekurencyjnie. Czy profesor żąda, abyś ty również był nieświadomy tych rzeczy?
Theodoros Chatzigiannakis

34
Profesor powinien zamiast tego przyznać mu dodatkowe uznanie za wymyślenie eleganckiego sposobu rozwiązania problemu lub, powiedzmy, nieszablonowe myślenie.

11
Jakie było zadanie? To jest problem, nad którym często się zastanawiałem, kiedy przesyłasz zadanie programistyczne, co jest zaznaczane, twoja zdolność do rozwiązania problemu lub twoja zdolność do wykorzystania tego, czego się nauczyłeś. Te dwie niekoniecznie są takie same.
Leon

35
FWIW, monitujący o wprowadzenie danych, dopóki nie jest to właściwe, nie jest dobrym miejscem do korzystania z rekursji, zbyt łatwo przepełnić stos. W tym konkretnym przypadku lepiej byłoby użyć czegoś takiego jak a() { do { good = prompt(); } while (!good); }.
Kevin

Odpowiedzi:


113

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.


8
Czy możesz rozwinąć swoje twierdzenie, że rekurencja nie jest funkcją? W mojej odpowiedzi argumentowałem, że tak jest, ponieważ nie wszystkie kompilatory koniecznie to obsługują.
Harry Johnston

5
Nie wszystkie języki również obsługują rekursję, więc niekoniecznie jest to tylko kwestia wyboru odpowiedniego kompilatora - ale masz rację, mówiąc, że „funkcja” jest z natury niejednoznacznym opisem, więc jest wystarczająco sprawiedliwy. Twoja druga uwaga jest również uczciwa z punktu widzenia osoby uczącej się programować (jak to jest obecnie zwykle) bez wcześniejszego przygotowania się do programowania w kodzie maszynowym. :-)
Harry Johnston

2
Zwróć uwagę, że problem „czytelności” jest związany ze składnią. W rekurencji nie ma nic „nieczytelnego”. W rzeczywistości indukcja jest najłatwiejszym sposobem wyrażania indukcyjnych struktur danych, takich jak pętle, listy, sekwencje i tak dalej. Większość struktur danych ma charakter indukcyjny.
nomen

6
Myślę, że ułożyłeś talię swoim sformułowaniem. Opisałeś wersję iteracyjną funkcjonalnie i na odwrót. Myślę, że bardziej sprawiedliwy opis, linia po linii, brzmiałby: „Poproszę o wprowadzenie danych. Jeśli dane wejściowe są nieprawidłowe, będę powtarzać monit, aż otrzymam prawidłowe dane. Wtedy go zwrócę ”. vs „Poproszę o wprowadzenie danych. Jeśli dane wejściowe są prawidłowe, zwrócę je. W przeciwnym razie zwrócę wynik powtórki. ” (Moje dzieci rozumiały funkcjonalną koncepcję powtórki, kiedy były w przedszkolu, więc myślę, że jest to uzasadnione angielskie podsumowanie koncepcji rekurencyjnej tutaj.)
pjs

2
@HarryJohnston Brak obsługi rekurencji byłby raczej wyjątkiem od istniejących funkcji niż brakiem nowej funkcji. W szczególności, w kontekście tego pytania, „nowa funkcja” oznacza „użyteczny zachowanie jeszcze nie nauczył istnieje”, co nie jest prawdą rekursji bo to logiczne rozszerzenie funkcji, które były nauczane (mianowicie, że procedury zawierać instrukcje, a wywołania procedur są instrukcjami). To tak, jakby profesor uczył studenta dodawania, a następnie skarcił go za dodanie tej samej wartości więcej niż jeden raz, ponieważ „nie omówiliśmy mnożenia”.
nmclean

48

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


Na przykład preprocesor C nie obsługuje rekursji w makrach. Definicje makr zachowują się podobnie do funkcji, ale nie można ich wywoływać rekurencyjnie.
sth

7
Twój „wymyślony przykład” to nie wszystko, co wymyślone: ​​standard Fortran 77 nie pozwalał funkcjom na nazywanie się rekurencyjnie - powodem jest to, co opisujesz. (Uważam, że adres, do którego należy przeskoczyć, gdy funkcja została wykonana, został zapisany na końcu samego kodu funkcji lub w czymś równoważnym z tym układem). Zobacz tutaj, aby dowiedzieć się trochę o tym.
alexis

5
Języki shaderów lub języki GPGPU (np. GLSL, Cg, OpenCL C) nie obsługują rekursji. O ile nie wszystkie języki go obsługują, z pewnością jest słuszny. Rekursji zakłada równoważnik stosu (to nie musi być koniecznie stos , ale nie musi być środkiem do przechowywania adresu powrotu i ramki funkcyjnych jakoś ).
Damon

Kompilator Fortrana, nad którym pracowałem trochę na początku lat 70., nie miał stosu wywołań. Każdy podprogram lub funkcja miała statyczne obszary pamięci dla adresu zwrotnego, parametrów i własnych zmiennych.
Patricia Shanahan

2
Nawet niektóre wersje Turbo Pascala domyślnie wyłączały rekurencję i trzeba było ustawić dyrektywę kompilatora, aby ją włączyć.
dan04

17

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


2
Nie kazano nam wykonywać tego zadania w żaden określony sposób; i poznaliśmy metody, a nie tylko iterację. Pozostawiłbym również ten, który jest łatwiejszy do odczytania, zgodnie z osobistymi preferencjami: wybrałem to, co dla mnie wyglądało dobrze. Błąd SO jest dla mnie nowy, chociaż idea, że ​​rekurencja jest funkcją samą w sobie, nadal nie wydaje się uzasadniona.

3
„Zostawiłbym ten, który jest łatwiejszy do odczytania zgodnie z osobistymi preferencjami”. Zgoda. Rekursja nie jest funkcją języka Java. To są.
mike

2
@Vality: Eliminacja wywołań ogonowych? Niektóre maszyny JVM mogą to robić, ale pamiętaj, że muszą również utrzymywać ślad stosu dla wyjątków. Jeśli pozwala na eliminację wywołań końcowych, ślad stosu, wygenerowany naiwnie, może stać się nieprawidłowy, więc niektóre maszyny JVM nie używają z tego powodu TCE.
icktoofay

5
Tak czy inaczej, poleganie na optymalizacji, aby Twój uszkodzony kod był mniej uszkodzony, jest dość złą formą.
cHao

7
+1, zobacz, że ostatnio w Ubuntu ekran logowania został uszkodzony, gdy użytkownik naciskał przycisk Enter w sposób ciągły, to samo stało się z XBox
Sebastian

13

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.


10

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


Celem samej metody jest sprawdzenie poprawności danych wejściowych, a następnie wywołanie i zwrócenie wyniku innej metody (dlatego zwraca ona samą siebie). Mówiąc dokładniej, sprawdza, czy ruch w grze Kółko i krzyżyk jest prawidłowy, a następnie wraca hasWon(x, y, piece)(aby sprawdzić tylko wiersz i kolumnę, na którą ma to wpływ).

możesz po prostu wziąć TYLKO część walidacyjną i umieścić ją w innej metodzie, na przykład „GetInput”, a następnie użyć jej tak, jak napisałem w mojej odpowiedzi. Zmieniłem moją odpowiedź, opisując, jak powinna wyglądać. Oczywiście możesz sprawić, że GetInput zwróci typ, który zawiera potrzebne informacje.
Yonatan Nir

1
Yonatan Nir: Kiedy rekurencja była złą praktyką? Może JVM wybuchnie, ponieważ maszyna wirtualna Hotspot nie może zoptymalizować z powodu bezpieczeństwa kodu bajtowego i tak byłoby fajnym argumentem. Czym różni się Twój kod od innego podejścia?

1
Rekursja nie zawsze jest złą praktyką, ale jeśli można jej uniknąć i zachować czysty i łatwy w utrzymaniu kod, należy jej unikać. W Javie, C i Pythonie rekurencja jest dość kosztowna w porównaniu z iteracją (ogólnie), ponieważ wymaga alokacji nowej ramki stosu. W niektórych kompilatorach C można użyć flagi kompilatora, aby wyeliminować ten narzut, który przekształca niektóre typy rekurencji (w rzeczywistości niektóre typy wywołań ogona) w skoki zamiast wywołań funkcji.
Yonatan Nir

1
Nie jest to jasne, ale jeśli zastąpisz pętlę nieokreśloną liczbą iteracji rekurencją, to źle. Java nie gwarantuje optymalizacji wywołań końcowych, więc łatwo może zabraknąć miejsca na stosie. W Javie nie używaj rekurencji, chyba że masz gwarancję ograniczonej liczby iteracji (zwykle logarytmicznych w porównaniu do całkowitego rozmiaru danych).
hyde

6

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.


1
Każdy potencjalnie ryzykowny algorytm rekurencyjny można zawsze przepisać w trywialny sposób, aby używał jawnego stosu - w końcu stos wywołań jest tylko stosem. W takim przypadku, gdybyś przepisał rozwiązanie tak, aby używał stosu, wyglądałoby to absurdalnie - kolejny dowód, że rekurencyjna odpowiedź nie jest zbyt dobra.
Aaronaught

1
Jeśli przepełnienia stosu stanowią problem, powinieneś użyć języka / środowiska wykonawczego, które obsługuje optymalizację wywołań końcowych, takiego jak .NET 4.0 lub dowolny funkcjonalny język programowania
Sebastian

Nie wszystkie rekursje są wywołaniami końcowymi.
Warren Dew

6

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.


1
To sprawiło, że moja głowa eksplodowała, zwłaszcza Unlambda +1
John Powell

Kombinatory punktów stałych są trudne. Kiedy zdecydowałem się nauczyć programowania funkcjonalnego, zmusiłem się do studiowania kombinatora Y, dopóki go nie zrozumiałem, a następnie zastosowałem go do napisania innych przydatnych funkcji. Zajęło mi to chwilę, ale było tego warte.
jagoda

5

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


Większość omawianej metody i celem samej metody polega na sprawdzaniu poprawności danych wejściowych za pomocą różnych kontroli. Proces rozpoczyna się od nowa, jeśli dane wejściowe są nieprawidłowe, dopóki dane wejściowe nie będą poprawne (zgodnie z instrukcją).

4
@fay Ale jeśli dane wejściowe są nieprawidłowe zbyt wiele razy, otrzymasz StackOverflowError. Rekursja jest bardziej elegancka, ale w moich oczach zwykle stanowi większy problem niż zwykła pętla (ze względu na stosy).
Michael Yaworski

1
To ciekawa i słuszna uwaga. Nie brałem pod uwagę tego błędu. Chociaż, czy ten sam efekt można osiągnąć, while(true)wywołując tę ​​samą metodę? Jeśli tak, nie powiedziałbym, że obsługuje to jakąkolwiek różnicę między rekurencją, dobrze wiedzieć, jaka jest.

1
@fay while(true)to nieskończona pętla. Jeśli nie masz breakoświadczenia, nie widzę w tym sensu, chyba że próbujesz zawiesić swój program lol. Chodzi mi o to, że jeśli wywołasz tę samą metodę (to jest rekurencja), czasami da ci ona StackOverflowError , ale jeśli użyjesz pętli whilelub for, nie będzie. Problem po prostu nie istnieje w przypadku zwykłej pętli. Może źle cię zrozumiałem, ale moja odpowiedź brzmi: nie.
Michael Yaworski

4
Wydaje mi się, że to prawdopodobnie prawdziwy powód, dla którego profesor zdjął oceny =) Być może nie wyjaśnił tego zbyt dobrze, ale słuszną skargą jest stwierdzenie, że używałeś go w sposób, który byłby uważany za bardzo kiepski styl, jeśli nie po prostu wadliwy w bardziej poważnym kodzie.
Commander Coriander Salamander

3

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.