Mówiąc wprost, czym jest rekurencja?

74

Idea rekurencji nie jest zbyt powszechna w prawdziwym świecie. Dla początkujących programistów wydaje się to nieco mylące. Sądzę jednak, że stopniowo przyzwyczajają się do tej koncepcji. Co może być dla nich dobrym wyjaśnieniem, aby łatwo zrozumieć pomysł?

Gulshan
źródło
Więcej informacji na ten temat można znaleźć na stronie Zasoby w celu lepszego zrozumienia rekurencji?
Kenneth
1
Rekurencja ma miejsce, gdy funkcja może się wywołać. „Jeśli całkowicie rozumiesz przestrzenie nazw i zakres oraz sposób przekazywania parametrów do funkcji, znasz już rekurencję. Mogę pokazać przykłady, ale powinieneś być w stanie dowiedzieć się, jak działają one samodzielnie”. Studenci na ogół zmagają się z rekurencją nie tyle dlatego, że jest to mylące, ale dlatego, że nie mają pewności w zakresie zmiennego zakresu / przestrzeni nazw. Przed zanurzeniem się w rekursji upewnij się, że uczniowie mogą poprawnie prześledzić program, w którym celowo nadałeś zmiennym w różnych zakresach tę samą nazwę, aby je pomylić.
dspyz
1
Aby zrozumieć rekurencję, musisz najpierw zrozumieć rekurencję
Goerman

Odpowiedzi:

110

Aby wyjaśnić rekurencję , używam kombinacji różnych wyjaśnień, zwykle w celu:

  • wyjaśnić pojęcie,
  • wyjaśnij, dlaczego to ma znaczenie,
  • wyjaśnij, jak to zdobyć.

Na początek Wolfram | Alpha definiuje to w prostszych terminach niż Wikipedia :

Wyrażenie takie, że każdy termin jest generowany przez powtórzenie określonej operacji matematycznej.


Matematyka

Jeśli twój uczeń (lub osoba, którą również wyjaśnisz, odtąd powiem studentowi) ma przynajmniej pewne podłoże matematyczne, najwyraźniej już spotkał się z rekurencją, studiując serie i ich pojęcie rekurencyjności oraz ich relację powtarzalności .

Bardzo dobrym sposobem na rozpoczęcie jest następnie zademonstrowanie za pomocą serii i powiedzenie, że po prostu chodzi o rekurencję:

  • funkcja matematyczna ...
  • ... który wywołuje się do obliczenia wartości odpowiadającej n-temu elementowi ...
  • ... i który określa pewne granice.

Zazwyczaj dostajesz „huh huh, whatev”, co najwyżej, ponieważ nadal go nie używają, lub bardziej prawdopodobne jest to bardzo głębokie chrapanie.


Przykłady kodowania

Co do reszty, to faktycznie szczegółowa wersja tego, co przedstawiono w uzupełnieniu do mojej odpowiedzi na pytania, które wskazał w zakresie wskaźników (zły pun).

Na tym etapie moi uczniowie zwykle wiedzą, jak wydrukować coś na ekranie. Zakładając, że używamy C, wiedzą, jak wydrukować pojedynczy znak za pomocą writelub printf. Wiedzą także o pętlach sterowania.

Zwykle uciekam się do kilku powtarzających się i prostych problemów programistycznych, dopóki ich nie otrzymają:

  • silnia operacja,
  • drukarka alfabetyczna,
  • drukarka z odwróconym alfabetem,
  • exponentation operacja.

Factorial

Factorial to bardzo prosta koncepcja matematyczna do zrozumienia, a jej implementacja jest bardzo zbliżona do jej matematycznej reprezentacji. Jednak na początku mogą go nie otrzymać.

Rekurencyjna definicja operacji czynnikowej

Alfabety

Wersja alfabetyczna jest interesująca, aby nauczyć ich myśleć o kolejności ich rekurencyjnych instrukcji. Podobnie jak w przypadku wskaźników, będą rzucać w ciebie losowo liniami. Chodzi o to, aby uświadomić im, że pętlę można odwrócić, modyfikując warunki LUB po prostu odwracając kolejność instrukcji w funkcji. Tutaj pomaga wydrukowanie alfabetu, ponieważ jest to dla nich coś wizualnego. Po prostu poproś, aby napisali funkcję, która wypisze jeden znak dla każdego wywołania i wywoła się rekurencyjnie, aby napisać następny (lub poprzedni).

Fani FP pomijają fakt, że drukowanie rzeczy do strumienia wyjściowego jest na razie efektem ubocznym ... Nie denerwujmy się na froncie FP. (Ale jeśli używasz języka z obsługą list, nie krępuj się łączyć z listą przy każdej iteracji i po prostu drukować końcowy wynik. Ale zwykle zaczynam je od C, co niestety nie jest najlepsze dla tego rodzaju problemów i koncepcji) .

Potęgowanie

Problem potęgowania jest nieco trudniejszy ( na tym etapie nauki). Oczywiście koncepcja jest dokładnie taka sama jak dla silni i nie ma dodatkowej złożoności ... oprócz tego, że masz wiele parametrów. I to zwykle wystarcza, aby zmylić ludzi i odrzucić ich na początku.

Jego prosta forma:

Prosta forma operacji potęgowania

można wyrazić w następujący sposób:

Relacja powtarzalności dla operacji potęgowania

Trudniej

Po pokazaniu tych prostych problemów ORAZ ponownym ich wdrożeniu w samouczkach możesz wykonać nieco trudniejsze (ale bardzo klasyczne) ćwiczenia:

Uwaga: Ponownie niektóre z nich nie są wcale trudniejsze ... Po prostu podchodzą do problemu dokładnie pod tym samym lub nieco innym kątem. Ale praktyka czyni mistrza.


Pomocnicy

Referencja

Niektóre czytanie nigdy nie boli. Na początku tak będzie, a oni poczują się jeszcze bardziej zagubieni. To coś, co rośnie na tobie i które siedzi z tyłu głowy, dopóki pewnego dnia nie zdasz sobie sprawy, że w końcu to dostałeś. A potem myślisz o tych rzeczach, które czytasz. Na razie wystarczyłyby rekursja , informatyka i strony z relacjami na Wikipedii.

Poziom / głębokość

Zakładając, że uczniowie nie mają dużego doświadczenia w programowaniu, zapewnij kody pośredniczące. Po pierwszych próbach daj im funkcję drukowania, która może wyświetlać poziom rekurencji. Pomaga wydrukowanie wartości liczbowej poziomu.

Diagram stosu jako szuflady

Wcięcie wydruku (lub wyniku poziomu) również pomaga, ponieważ daje kolejną wizualną reprezentację tego, co robi Twój program, otwierając i zamykając konteksty stosu, takie jak szuflady lub foldery w eksploratorze systemu plików.

Akronimy rekurencyjne

Jeśli twój uczeń jest już trochę zaznajomiony z kulturą komputerową, może już korzystać z niektórych projektów / oprogramowania o nazwach wykorzystujących rekurencyjne akronimy . Od pewnego czasu jest to tradycja, szczególnie w projektach GNU. Niektóre przykłady obejmują:

Rekurencyjne:

  • GNU - „GNU nie jest uniksem”
  • Nagios - „Nagios nie będzie nalegał na Sainthood”
  • PHP - „Preprocesor hipertekstu PHP” (i oryginalna „Osobista strona główna”)
  • Wino - „Wine Is Not an Emulator”
  • Zile - „Zile Is Lossy Emacs”

Wzajemnie rekurencyjne:

  • HURD - „HIRD demonów zastępujących Uniksa” (gdzie HIRD to „HURD interfejsów reprezentujących głębokość”)

Niech spróbują wymyślić własne.

Podobnie istnieje wiele przypadków rekurencyjnego humoru, takich jak rekurencyjna korekta wyszukiwania Google . Aby uzyskać więcej informacji na temat rekurencji, przeczytaj tę odpowiedź .


Pułapki i dalsza nauka

Niektóre problemy, z którymi zwykle borykają się ludzie i na które musisz znać odpowiedzi.

Dlaczego, o Boże, dlaczego?

Dlaczego chcesz to zrobić? Dobrym, ale nieoczywistym powodem jest to, że często łatwiej jest wyrazić w ten sposób problem. Niezbyt dobrym, ale oczywistym powodem jest to, że często wymaga mniej pisania na klawiaturze (nie sprawiając, że czują się tak lojalni po prostu za pomocą rekurencji ...).

Niektóre problemy są zdecydowanie łatwiejsze do rozwiązania przy zastosowaniu podejścia rekurencyjnego. Zazwyczaj każdy problem, który można rozwiązać za pomocą paradygmatu Divide and Conquer , pasuje do wielorakiego algorytmu rekurencyjnego.

Co znowu N?

Dlaczego moja nlub (niezależnie od nazwy zmiennej) za każdym razem jest inna? Początkujący zazwyczaj mają problem ze zrozumieniem, czym jest zmienna i parametr oraz jak rzeczy nazwane nw twoim programie mogą mieć różne wartości. Więc teraz, jeśli ta wartość znajduje się w pętli sterowania lub rekurencji, jest jeszcze gorzej! Bądź miły i nie używaj wszędzie tych samych nazw zmiennych i wyraź, że parametry są tylko zmiennymi .

Warunki końcowe

Jak określić stan końcowy? To proste, po prostu niech mówią głośno. Na przykład dla silni zacznij od 5, następnie 4, a następnie ... aż do 0.

Diabeł tkwi w szczegółach

Nie rozmawiaj o wczesnych rzeczach, takich jak optymalizacja wezwania ogona . Wiem, wiem, TCO jest fajne, ale na początku ich to nie obchodzi. Daj im trochę czasu na owinięcie głowy procesem w sposób, który będzie dla nich odpowiedni. Zachęcamy do późniejszego rozbicia ich świata, ale dajcie im spokój.

Podobnie, nie mów prosto z pierwszego wykładu o stosie wywołań i zużyciu pamięci i ... cóż ... przepełnienie stosu . Często prowadzę prywatne zajęcia dla nauczycieli, którzy pokazują mi wykłady, na których mają 50 slajdów o wszystkim, co należy wiedzieć o rekurencji, kiedy na tym etapie ledwo potrafią poprawnie napisać pętlę. To dobry przykład tego, jak odniesienie pomoże później , ale teraz po prostu myli cię głęboko.

Ale proszę we właściwym czasie wyjaśnić, że istnieją powody, aby wybrać trasę iteracyjną lub rekurencyjną .

Wzajemna rekurencja

Widzieliśmy, że funkcje mogą być rekurencyjne, a nawet mogą mieć wiele punktów wywoławczych (8-królowych, Hanoi, Fibonacciego, a nawet algorytm eksploracji trałowca). Ale co z wzajemnie rekurencyjnymi połączeniami ? Zacznij od matematyki tutaj. f(x) = g(x) + h(x)gdzie g(x) = f(x) + l(x)a hi lpo prostu zrobić rzeczy.

Rozpoczynanie od samych serii matematycznych ułatwia pisanie i implementację, ponieważ wyrażenia jasno definiują kontrakt. Na przykład sekwencje żeńskie i męskie Hofstadter :

Sekwencje męskie i żeńskie Hofstadtera

Jednak jeśli chodzi o kod, to należy zauważyć, że realizacja wzajemnie rekurencyjne rozwiązania często prowadzi do powielania kodu, a raczej powinno być usprawnione w pojedynczą postać rekurencyjną (Patrz Peter Norvig „s Rozwiązywanie Każdy Sudoku .

haylem
źródło
5
Czytam twoją odpowiedź po zobaczeniu jej po prawie 5 lub 6 raz. Myślę, że było to miłe, ale zbyt długie, aby przyciągnąć tu innych użytkowników. Nauczyłem się tutaj wielu rzeczy o nauczaniu rekurencji. Jako nauczyciel, czy mógłbyś ocenić mój pomysł na nauczanie rekursji- programmers.stackexchange.com/questions/25052/...
Gulshan,
9
@Gulshan, myślę, że ta odpowiedź jest tak obszerna, jak to tylko możliwe, i jest łatwa do przejrzenia przez zwykłego czytelnika. Dlatego dostaje static unsigned int vote = 1;ode mnie. Wybacz statyczny humor, jeśli chcesz :) To najlepsza jak dotąd odpowiedź.
Tim Post
1
@Gulsan: tylko ten, kto chce się uczyć, jest gotowy poświęcić trochę czasu, jest właściwie :) Nie mam nic przeciwko. Czasami krótka odpowiedź jest elegancka i zawiera wiele przydatnych i niezbędnych informacji, aby rozpocząć lub wyjaśnić ogólną koncepcję. Chciałem tylko na dłuższą odpowiedź na to pytanie, a biorąc pod uwagę, że PO wspomina o pytaniu, na które otrzymałem „poprawną” odpowiedź i zadaje podobną odpowiedź, uznałem, że należy udzielić takiej samej odpowiedzi. Cieszę się, że czegoś się nauczyłeś.
haylem,
@Gulshan: Jeśli chodzi o twoją odpowiedź: pierwszy punkt bardzo mnie zdezorientował, muszę powiedzieć. Podoba mi się, że opisujesz pojęcie funkcji rekurencyjnych jako coś, co zmienia się stopniowo w miarę upływu czasu, ale myślę, że twój sposób prezentacji jest nieco dziwny. Po przeczytaniu 3 punktów nie spodziewałbym się, że wielu uczniów nagle będzie w stanie rozwiązać Hanoi. Ale może to być tylko kwestia sformułowania.
haylem,
Natknąłem się na dobry sposób pokazania, że ​​ta sama zmienna może mieć różne wartości w różnych głębokościach rekurencji: zastanów się, czy uczniowie zapisują kroki, które podejmują, oraz wartości zmiennych, postępując zgodnie z pewnym rekurencyjnym kodem. Kiedy osiągną rekurencję, niech zaczną od nowa od nowa. Gdy osiągną warunek wyjścia, niech wrócą do poprzedniego elementu. Jest to zasadniczo emulacja stosu wywołań, ale jest to dobry sposób na pokazanie tych różnic.
Andy Hunt
58

Wywołanie funkcji z tej samej funkcji.

ChaosPandion
źródło
2
To jest najlepsze wytłumaczenie na początek. Prosto i na temat; po ustaleniu tego podsumowania przejdź do wszystkich szczegółów wycieczki.
jhocking
27

Rekurencja to funkcja, która sama się nazywa.

Jak go używać, kiedy go używać i jak uniknąć złego projektu, ważne jest, aby wiedzieć, co wymaga samodzielnego wypróbowania go i zrozumienia, co się stanie.

Najważniejszą rzeczą, którą musisz wiedzieć, to być bardzo ostrożnym, aby nie uzyskać pętli, która nigdy się nie kończy. Odpowiedź pramodc84 na twoje pytanie zawiera następującą usterkę: nigdy się nie kończy ...
Funkcja rekurencyjna musi zawsze sprawdzać warunek, aby ustalić, czy powinna się ponownie wywołać, czy nie.

Najbardziej klasycznym przykładem użycia rekurencji jest praca z drzewem bez statycznych ograniczeń głębokości. Jest to zadanie, które musisz użyć rekurencji.

respekt
źródło
Nadal możesz zaimplementować swój ostatni akapit w sposób iteracyjny, chociaż rekurencyjnie byłoby oczywiście lepiej. „Jak z niego korzystać, kiedy go używać i jak unikać złego projektu, należy wiedzieć, co wymaga samodzielnego wypróbowania go i zrozumienia, co się stanie.” Pomyślałem, że celem pytania jest uzyskanie wyjaśnienia tego rodzaju rzeczy.
haylem,
@haylem: Masz rację co do odpowiedzi na pytanie: „Jak go używać, kiedy go używać i jak uniknąć złego projektu ..” byłoby bardziej na miejscu, o co prosi OP (nie tylko „wypróbuj samemu „jak powiedziałem), ale wymagałoby to obszernego wykładu o charakterze bardziej dydaktycznym niż szybkiej odpowiedzi na pytanie tutaj. Wykonałeś jednak bardzo dobrą robotę z odpowiedzią . +1 za to ... Ci, którzy naprawdę potrzebują lepszego zrozumienia tej koncepcji, skorzystają na przeczytaniu Twojej odpowiedzi.
respekt
co z parą funkcji, które się nawzajem wywołują? A wzywa B, który wywołuje A ponownie, dopóki nie zostanie spełniony jakiś warunek. czy nadal będzie to uważane za rekurencję?
santiagozky
Tak, funkcja anadal wywołuje siebie, tylko pośrednio (przez wywołanie b).
uprzejmie
1
@santiagozky: Jak powiedział uprzejmy , wciąż jest to rekursja. Jednak zalecałbym tego nie robić. Podczas korzystania z rekurencji w kodzie powinno być bardzo jasne, że rekurencja jest na miejscu. Jeśli wywołuje się pośrednio przez inną funkcję, znacznie trudniej jest zobaczyć, co się dzieje. Jeśli nie wiesz, że funkcja wywołuje się sama, możesz znaleźć się w sytuacji, w której Ty (lub ktoś, kto nie utworzył tej funkcji) złamiesz jakiś warunek rekurencji (zmieniając funkcjonalność w kodzie) i zakończysz w martwym punkcie z niekończącą się pętlą.
awe
21

Programowanie rekurencyjne to proces stopniowego zmniejszania problemu w celu łatwiejszego rozwiązywania jego wersji.

Każda funkcja rekurencyjna ma tendencję do:

  1. weź listę do przetworzenia lub inną strukturę lub domenę problemów
  2. radzić sobie z bieżącym punktem / krokiem
  3. wywoływać się na reszcie / subdomenach
  4. połączyć lub wykorzystać wyniki pracy poddomeny

Kiedy krok 2 jest przed 3, a gdy krok 4 jest trywialny (konkatenacja, suma lub nic), umożliwia to rekurencję ogona . Krok 2 często musi nastąpić po kroku 3, ponieważ wyniki z subdomeny problemu mogą być potrzebne do ukończenia bieżącego kroku.

Przejdź przez proste drzewo binarne. Przechodzenie można wykonać w przedsprzedaży, w kolejności lub po zamówieniu, w zależności od potrzeb.

   B
A     C

Przedsprzedaż: BAC

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

W kolejności: ABC

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

Po zamówieniu: ACB

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Bardzo wiele problemów rekurencyjnych to konkretne przypadki operacji na mapie lub fold - zrozumienie tylko tych dwóch operacji może prowadzić do znacznego zrozumienia dobrych przypadków użycia dla rekurencji.

Orbling
źródło
Kluczowym elementem praktycznej rekurencji jest pomysł zastosowania rozwiązania nieco mniejszego problemu do rozwiązania większego. W przeciwnym razie po prostu masz nieskończoną rekurencję.
Barry Brown,
@Barry Brown: Całkiem słusznie. Stąd moje stwierdzenie „... zmniejszając problem do łatwiejszych do rozwiązania wersji”
Orbling
Niekoniecznie powiedziałbym tak ... Często tak jest, szczególnie w przypadku problemów z dzieleniem i podbijaniem lub w sytuacjach, w których naprawdę definiujesz relację powtarzalności, która sprowadza się do prostej sprawy. Ale powiedziałbym, że chodzi bardziej o udowodnienie, że dla każdej iteracji N twojego problemu istnieje przypadek obliczalny N + 1.
Haylem
1
@Sean McMillan: Recursion to potężne narzędzie, gdy jest używane w domenach, które mu odpowiadają. Zbyt często widzę, że jest to sprytny sposób radzenia sobie z jakimś stosunkowo trywialnym problemem, który masowo zaciemnia prawdziwą naturę wykonywanego zadania.
Orbling
20

OP powiedział, że rekurencja nie istnieje w prawdziwym świecie, ale błagam, by się różnić.

Weźmy prawdziwą „operację” cięcia pizzy. Wyjąłeś pizzę z piekarnika i aby ją podać, musisz pokroić ją na pół, a następnie pokroić na pół, a następnie pokroić na pół.

Operację krojenia pizzy wykonujesz wielokrotnie i dopóki nie uzyskasz pożądanego rezultatu (liczba plasterków). A dla argumentów powiedzmy, że nieoszlifowana pizza jest samym plasterkiem.

Oto przykład w Ruby:

def cut_pizza (istniejące_laski, pożądane_lice)
  if exist_slices! = pożądane_laski
    # nie mamy jeszcze wystarczającej liczby plasterków, aby nakarmić wszystkich, więc
    # kroimy plastry pizzy, podwajając ich liczbę
    new_slices = exist_slices * 2 
    # a to jest połączenie rekurencyjne
    cut_pizza (new_slices, pożądane_slice)
  jeszcze
    # mamy żądaną liczbę plasterków, więc wracamy
    # tutaj zamiast kontynuować
    zwróć istniejące_laski
  koniec
koniec

pizza = 1 # cała pizza, „jeden plasterek”
cut_pizza (pizza, 8) # => dostaniemy 8

Tak więc operacja w prawdziwym świecie to krojenie pizzy, a rekursja robi to samo w kółko, dopóki nie będziesz mieć tego, czego chcesz.

Operacje, które można zaimplementować za pomocą funkcji rekurencyjnych, to:

  • Obliczanie odsetek składanych w ciągu kilku miesięcy.
  • Szukanie pliku w systemie plików (ponieważ systemy plików są drzewami z powodu katalogów).
  • Chyba wszystko, co wiąże się z pracą z drzewami.

Polecam napisanie programu, który szukałby pliku na podstawie jego nazwy, i spróbuję napisać funkcję, która wywołuje się sama, dopóki nie zostanie znaleziona. Podpis wyglądałby następująco:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

Możesz więc nazwać to tak:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find apache's conf

Moim zdaniem jest to po prostu programowanie mechaniki, sposób na sprytne usunięcie duplikacji. Możesz przepisać to za pomocą zmiennych, ale jest to „ładniejsze” rozwiązanie. Nie ma w tym nic tajemniczego ani trudnego. Napisz kilka rekurencyjnych funkcji, kliknie i wywoła kolejną mechaniczną sztuczkę w oknie narzędzi programistycznych.

Dodatkowy kredyt Powyższy cut_pizzaprzykład da ci zbyt duży błąd poziomu stosu, jeśli poprosisz go o liczbę plasterków, która nie jest potęgą 2 (tj. 2 lub 4 lub 8 lub 16). Czy możesz go zmodyfikować, aby jeśli ktoś poprosił o 10 plasterków, nie działałby na zawsze?

Ryan Allen
źródło
16

Dobra, postaram się zachować to proste i zwięzłe.

Funkcja rekurencyjna to funkcje, które wywołują się same. Funkcja rekurencyjna składa się z trzech rzeczy:

  1. Logika
  2. Wezwanie do siebie
  3. Kiedy zakończyć?

Najlepszym sposobem na pisanie metod rekurencyjnych jest myślenie o metodzie, którą próbujesz napisać, jako prostym przykładzie obsługującym tylko jedną pętlę procesu, który chcesz powtórzyć, a następnie dodaj wywołanie do samej metody i dodaj, kiedy chcesz zakończyć. Najlepszym sposobem na naukę jest ćwiczenie jak wszystkie rzeczy.

Ponieważ jest to strona dla programistów, powstrzymam się od pisania kodu, ale tutaj jest dobry link

jeśli masz ten dowcip, rozumiesz, co oznacza rekurencja.

zakurzony programista
źródło
Zobacz także tę odpowiedź: programmers.stackexchange.com/questions/25052/… (-:
Murph
4
Ściśle, rekurencja nie wymaga warunku zakończenia; zagwarantowanie, że rekurencja zakończy się, ogranicza rodzaje problemów, które funkcja rekurencyjna może rozwiązać, i istnieją pewne typy prezentacji semantycznych, które w ogóle nie wymagają zakończenia.
Donal Fellows,
6

Rekurencja jest narzędziem, którego programista może użyć do wywołania wywołania funkcji na sobie. Sekwencja Fibonacciego to podręcznikowy przykład użycia rekurencji.

Większość kodu rekurencyjnego, jeśli nie wszystkie, można wyrazić jako funkcję iteracyjną, ale zwykle jest on nieporządny. Dobrym przykładem innych programów rekurencyjnych są struktury danych, takie jak drzewa, drzewo wyszukiwania binarnego, a nawet szybkie sortowanie.

Rekurencja służy do tego, aby kod był mniej niechlujny, należy pamiętać, że zwykle jest wolniejszy i wymaga więcej pamięci.

Bryan Harrington
źródło
To, czy jest wolniejsze, czy wymaga więcej pamięci, zależy bardzo od użytego narzędzia.
Orbling
5
Obliczanie sekwencji Fibonacciego to straszna rzecz rekurencyjnie. Przechodzenie przez drzewa jest znacznie bardziej naturalnym wykorzystaniem rekurencji. Zazwyczaj, gdy rekursja jest dobrze używana, nie jest wolniejsza i nie wymaga więcej pamięci, ponieważ musiałbyś zachować własny stos zamiast stosu wywołań.
David Thornley,
1
@Dave: Nie kwestionowałbym tego, ale myślę, że Fibonacci jest dobrym przykładem na początek.
Bryan Harrington,
5

Lubię używać tego:

Jak idziesz do sklepu?

Jeśli jesteś przy wejściu do sklepu, po prostu przejdź przez niego. W przeciwnym razie zrób jeden krok, a następnie przejdź resztę drogi do sklepu.

Ważne jest, aby uwzględnić trzy aspekty:

  • Trywialna skrzynka podstawowa
  • Rozwiązanie małego fragmentu problemu
  • Rozwiązanie reszty problemu rekurencyjnie

W rzeczywistości często używamy rekurencji w życiu codziennym; po prostu nie myślimy o tym w ten sposób.

Barry Brown
źródło
To nie jest rekurencja. Byłoby tak, gdybyś podzielił go na dwie części: idź w połowie drogi do sklepu, idź w drugiej połowie. Powtórz.
2
To jest rekurencja. To nie jest podział i podbój, ale to tylko jeden rodzaj rekurencji. Algorytmy grafów (takie jak wyszukiwanie ścieżek) są pełne pojęć rekurencyjnych.
deadalnix
2
To jest rekurencja, ale uważam to za kiepski przykład, ponieważ zbyt łatwo mentalnie przetłumaczyć „zrób jeden krok, a następnie przejdź resztę do sklepu” na algorytm iteracyjny. Wydaje mi się, że jest to równoważne z przekształceniem ładnie napisanej forpętli w bezsensowną funkcję rekurencyjną.
Brian
3

Najlepszym przykładem, na który chciałbym wskazać, jest C Programming Language autorstwa K & R. strona indeksu również.

Kanini
źródło
2

Josh K wspomniał już o lalkach Matroshka . Załóżmy, że chcesz się nauczyć czegoś, co zna tylko najkrótsza lalka. Problem polega na tym, że tak naprawdę nie można z nią rozmawiać bezpośrednio, ponieważ ona pierwotnie mieszka w wyższej lalce, która na pierwszym zdjęciu znajduje się po jej lewej stronie. Ta struktura wygląda tak (lalka mieszka w wyższej lalce), aż kończy się tylko najwyższą.

Jedyne, co możesz zrobić, to zadać pytanie najwyższej lalce. Najwyższa lalka (która nie zna odpowiedzi) będzie musiała przekazać twoje pytanie krótszej lalce (która na pierwszym zdjęciu jest po jej prawej stronie). Ponieważ ona również nie ma odpowiedzi, musi zapytać następną krótszą lalkę. Tak będzie, dopóki wiadomość nie dotrze do najkrótszej lalki. Najkrótsza lalka (która jako jedyna zna tajną odpowiedź) przekaże odpowiedź następnej wyższej lalce (znalezionej po jej lewej stronie), która przekaże ją następnej wyższej lalce ... i będzie to trwało do momentu odpowiedzi dociera do miejsca docelowego, czyli najwyższej lalki i wreszcie ... ciebie :)

To właśnie robi rekursja. Funkcja / metoda wywołuje się do momentu otrzymania oczekiwanej odpowiedzi. Dlatego podczas pisania kodu rekurencyjnego bardzo ważne jest, aby zdecydować, kiedy rekurencja powinna się zakończyć.

Nie jest to najlepsze wytłumaczenie, ale mam nadzieję, że pomaga.

sakisk
źródło
2

Rekursja n. - Wzorzec projektowania algorytmów, w którym operacja jest definiowana sama w sobie.

Klasycznym przykładem jest znalezienie silni liczby, n !. 0! = 1, a dla każdej innej liczby naturalnej N silnia N jest iloczynem wszystkich liczb naturalnych mniejszych lub równych N. Zatem 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Ta podstawowa definicja pozwoli ci stworzyć proste iteracyjne rozwiązanie:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

Sprawdź jednak ponownie operację. 6! = 6 * 5 * 4 * 3 * 2 * 1. Według tej samej definicji 5! = 5 * 4 * 3 * 2 * 1, co oznacza, że ​​możemy powiedzieć 6! = 6 * (5!). Z kolei 5! = 5 * (4!) I tak dalej. W ten sposób redukujemy problem do operacji wykonanej na podstawie wyników wszystkich poprzednich operacji. To ostatecznie redukuje się do punktu, zwanego przypadkiem podstawowym, w którym wynik jest znany z definicji. W naszym przypadku 0! = 1 (w większości przypadków moglibyśmy również powiedzieć, że 1! = 1). W obliczeniach często możemy definiować algorytmy w bardzo podobny sposób, wywołując samą metodę i przekazując mniejszą liczbę danych wejściowych, co zmniejsza problem przez wiele rekurencji do przypadku podstawowego:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

W wielu językach można to jeszcze uprościć za pomocą operatora trójskładnikowego (czasami postrzeganego jako funkcja Iif w językach, które nie zapewniają operatora jako takiego):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Zalety:

  • Wyrażenie naturalne - w przypadku wielu rodzajów algorytmów jest to bardzo naturalny sposób wyrażenia funkcji.
  • Zredukowany LOC - często rekurencyjnie jest definiować funkcję w sposób bardziej zwięzły.
  • Szybkość - w niektórych przypadkach, w zależności od języka i architektury komputera, rekurencja algorytmu jest szybsza niż równoważne iteracyjne rozwiązanie, zwykle dlatego, że wywołanie funkcji jest szybsze na poziomie sprzętowym niż operacje i dostęp do pamięci wymagany do iteracyjnego zapętlenia.
  • Podzielność - wiele rekurencyjnych algorytmów ma mentalność „dziel i rządź”; wynik operacji jest funkcją wyniku tej samej operacji wykonanej na każdej z dwóch połówek wejścia. Pozwala to na podzielenie pracy na dwie części na każdym poziomie, a jeśli to możliwe, możesz przekazać drugą połowę innej „jednostce wykonawczej” do przetworzenia. Jest to zwykle trudniejsze lub niemożliwe przy zastosowaniu algorytmu iteracyjnego.

Niedogodności:

  • Wymaga zrozumienia - musisz po prostu „zrozumieć” koncepcję rekurencji, aby zrozumieć, co się dzieje, a zatem napisać i utrzymywać skuteczne algorytmy rekurencyjne. W przeciwnym razie wygląda to jak czarna magia.
  • Zależny od kontekstu - to, czy rekurencja jest dobrym pomysłem, zależy od tego, jak elegancko algorytm może być zdefiniowany sam w sobie. Chociaż możliwe jest zbudowanie, na przykład, rekurencyjnego SelectionSort, iteracyjny algorytm jest zazwyczaj bardziej zrozumiały.
  • Dostęp do pamięci RAM dla stosu wywołań - zwykle wywołania funkcji są tańsze niż dostęp do pamięci podręcznej, co może sprawić, że rekursja będzie szybsza niż iteracja. Ale zwykle istnieje ograniczenie głębokości stosu wywołań, które może powodować rekurencję do błędu, w którym zadziała algorytm iteracyjny.
  • Nieskończona rekurencja - musisz wiedzieć, kiedy przestać. Możliwa jest również nieskończona iteracja, ale zaangażowane konstrukcje zapętlania są zwykle łatwiejsze do zrozumienia, a tym samym do debugowania.
KeithS
źródło
1

Przykład, którego używam, to problem, z którym się spotkałem w prawdziwym życiu. Masz pojemnik (taki jak duży plecak, który zamierzasz zabrać na wycieczkę) i chcesz poznać całkowitą wagę. Masz w pojemniku dwa lub trzy luźne przedmioty i niektóre inne pojemniki (powiedzmy worki na rzeczy). Ciężar całego pojemnika to oczywiście ciężar pustego pojemnika plus ciężar wszystkiego w nim. W przypadku przedmiotów sypkich można je po prostu zważyć, a w przypadku worków z rzeczami można je po prostu zważyć lub powiedzieć „no cóż, waga każdego z worków to waga pustego pojemnika plus waga wszystkiego w nim”. A potem wchodzisz do pojemników do pojemników i tak dalej, aż dojdziesz do punktu, w którym są tylko luźne przedmioty w pojemniku. To jest rekurencja.

Może się wydawać, że tak się nie dzieje w rzeczywistości, ale wyobraź sobie, że próbujesz policzyć lub zsumować pensje osób w konkretnej firmie lub oddziale, które zawierają mieszankę ludzi, którzy po prostu pracują dla firmy, ludzi w oddziałach, a następnie w podziały są wydziały i tak dalej. Lub sprzedaż w kraju, który ma regiony, niektóre z nich mają podregiony itp. Tego rodzaju problemy zdarzają się cały czas w biznesie.

Kate Gregory
źródło
0

Rekurencja może być wykorzystana do rozwiązania wielu problemów z liczeniem. Załóżmy na przykład, że masz grupę n osób na imprezie (n> 1) i wszyscy podają sobie rękę dokładnie raz. Ile ma miejsce uścisków dłoni? Możesz wiedzieć, że rozwiązaniem jest C (n, 2) = n (n-1) / 2, ale możesz rozwiązać rekurencyjnie w następujący sposób:

Załóżmy, że są tylko dwie osoby. Wtedy (przez kontrolę) odpowiedź brzmi oczywiście 1.

Załóżmy, że masz trzy osoby. Wyróżnij jedną osobę i zwróć uwagę, że ona / ona ściska ręce dwóm innym osobom. Następnie musisz policzyć tylko uściski dłoni między pozostałymi dwiema osobami. Zrobiliśmy to już teraz i jest to 1. Więc odpowiedź to 2 + 1 = 3.

Załóżmy, że masz n ludzi. Zgodnie z tą samą logiką, co poprzednio, jest to (n-1) + (liczba uścisków dłoni między n-1 osobami). Rozwijając się, otrzymujemy (n-1) + (n-2) + ... + 1.

Wyrażony jako funkcja rekurencyjna,

f (2) = 1
f (n) = n-1 + f (n-1), n> 2

Mitch Schwartz
źródło
0

W życiu (w przeciwieństwie do programu komputerowego) rekurencja rzadko zdarza się pod naszą bezpośrednią kontrolą, ponieważ może być myląca. Ponadto postrzeganie zwykle dotyczy efektów ubocznych, a nie funkcjonalnej czystości, więc jeśli nastąpi rekurencja, możesz tego nie zauważyć.

Jednak na świecie zdarza się rekurencja. Dużo.

Dobrym przykładem jest (uproszczona wersja) obieg wody:

  • Słońce ogrzewa jezioro
  • Woda unosi się w niebo i tworzy chmury
  • Chmury dryfują w stronę góry
  • W górach powietrze staje się zbyt zimne, aby zatrzymać wilgoć
  • Pada deszcz
  • Powstaje rzeka
  • Woda w rzece wpada do jeziora

Jest to cykl, który powoduje, że jego ja ponownie się dzieje. Jest rekurencyjny.

Innym miejscem, w którym można uzyskać rekursję, jest angielski (i ogólnie ludzki język). Na początku możesz go nie rozpoznać, ale sposób, w jaki możemy wygenerować zdanie, jest rekurencyjny, ponieważ reguły pozwalają nam osadzić jedno wystąpienie symbolu obok drugiego wystąpienia tego samego symbolu.

Instynkt językowy Stevena Pinkera:

jeśli albo dziewczyna je lody, albo dziewczynka je słodycze, to chłopiec je hot dogi

To całe zdanie, które zawiera inne całe zdania:

dziewczyna je lody

dziewczyna je słodycze

chłopiec je hot dogi

Akt zrozumienia pełnego zdania polega na zrozumieniu mniejszych zdań, które wykorzystują ten sam zestaw sztuczek umysłowych, aby być rozumianym jako pełne zdanie.

Aby zrozumieć rekurencję z perspektywy programowania, najłatwiej jest spojrzeć na problem, który można rozwiązać za pomocą rekurencji, i zrozumieć, dlaczego powinna być i co to oznacza, że ​​musisz zrobić.

Na przykład użyję największej wspólnej funkcji dzielnika, w skrócie gcd.

Masz dwie liczby ai b. Aby znaleźć ich gcd (przy założeniu, że nie ma wartości 0), musisz sprawdzić, czy amożna go równomiernie podzielić b. Jeśli tak, to bjest gcd, w przeciwnym razie musisz sprawdzić gcd bi resztę a/b.

Powinieneś już być w stanie zobaczyć, że jest to funkcja rekurencyjna, ponieważ masz funkcję gcd wywołującą funkcję gcd. Po prostu wbij go do domu, oto jest w c # (ponownie, zakładając, że 0 nigdy nie zostanie przekazane jako parametr):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

W programie ważne jest, aby mieć stan zatrzymania, w przeciwnym razie funkcja będzie się powtarzać na zawsze, co ostatecznie spowoduje przepełnienie stosu!

Powodem użycia tutaj rekurencji zamiast pętli while lub innej iteracyjnej konstrukcji jest to, że podczas czytania kodu mówi on, co robi i co będzie dalej, więc łatwiej jest ustalić, czy działa poprawnie .

Matt Ellen
źródło
1
Przykład cyklu wodnego był iteracyjny. Drugi przykład językowy wydaje się bardziej dzielić i podbijać niż rekursja.
Gulshan,
@Gulshan: Powiedziałbym, że cykl wody jest rekurencyjny, ponieważ powoduje, że jego jaźń się powtarza, jak funkcja rekurencyjna. To nie jest jak malowanie pokoju, w którym wykonuje się ten sam zestaw kroków na kilku obiektach (ścianach, suficie itp.), Jak w pętli for. Przykład języka używa dzielenia i podbijania, ale także „funkcja”, która jest nazywana, wywołuje swoją pracę nad zagnieżdżonymi zdaniami, więc jest rekurencyjna w ten sposób.
Matt Ellen,
W cyklu wodnym cykl rozpoczyna się od słońca i żaden inny element cyklu nie powoduje, że słońce zaczyna od nowa. Więc gdzie jest połączenie rekurencyjne?
Gulshan,
Nie ma połączenia rekurencyjnego! To nie jest funkcja. : D Jest rekurencyjny, ponieważ powoduje, że jego jaźń się powtarza. Woda z jeziora wraca do jeziora i cykl zaczyna się od nowa. Jeśli jakiś inny system wlewałby wodę do jeziora, to byłby iteracyjny.
Matt Ellen,
1
Cykl wodny to pętla while. Oczywiście, pętla while może być wyrażona za pomocą rekurencji, ale zrobienie tego spowoduje wysadzenie stosu. Proszę nie.
Brian
0

Oto rzeczywisty przykład rekurencji.

Pozwól im sobie wyobrazić, że mają kolekcję komiksów, a wszystko zmieszycie w jeden wielki stos. Ostrożnie - jeśli naprawdę mają kolekcję, mogą natychmiast cię zabić, gdy tylko wspomnisz o tym, aby to zrobić.

Teraz pozwól im posortować ten duży, nieposortowany stos komiksów za pomocą tego podręcznika:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

Dobrą rzeczą jest to, że gdy sprowadzają się do pojedynczych problemów, mają pełną „ramkę stosu” z lokalnymi stosami widocznymi przed nimi na ziemi. Daj im wiele wydruków instrukcji i odłóż po jednym na każdy poziom stosu ze znakiem, w którym aktualnie jesteś na tym poziomie (tj. Stan zmiennych lokalnych), abyś mógł kontynuować tam na każdym Gotowym.

Właśnie o to chodzi w rekurencji: wykonywanie tego samego procesu, na bardziej szczegółowym poziomie, im więcej się w to zagłębia.

Bezpieczne
źródło
-1
  • Zakończ, jeśli warunek wyjścia został osiągnięty
  • zrób coś, aby zmienić stan rzeczy
  • wykonuj pracę od nowa, zaczynając od obecnego stanu rzeczy

Rekursja to bardzo zwięzły sposób wyrażenia czegoś, co należy powtarzać, aż coś zostanie osiągnięte.

vpit3833
źródło
-1

Nie zwykły angielski, nie tak naprawdę przykłady z prawdziwego życia, ale dwa sposoby uczenia się rekurencji poprzez grę:

mouviciel
źródło
-2

Ładne wyjaśnienie rekurencji jest dosłownie „działaniem, które powraca od wewnątrz”.

Pomyśl o malarzu malującym ścianę, jest to rekurencyjne, ponieważ akcja polega na „pomalowaniu paska od sufitu do podłogi, a następnie przesunięciu go nieco w prawo i (pomalowaniu paska od sufitu do podłogi, a następnie przesunięciu go trochę w prawo i (pomaluj rozebrać się od sufitu do podłogi, a następnie przesunąć nieco w prawo i (itp.)) ”

Jego funkcja paint () wywołuje się w kółko, tworząc większą funkcję paint_wall ().

Mam nadzieję, że ten biedny malarz ma jakiś stan zatrzymania :)

Dan1ell
źródło
6
Dla mnie przykład wydaje się bardziej procedurą iteracyjną, a nie rekurencyjną.
Gulshan,
@Gulshan: Rekursja i iteracja robią podobne rzeczy, a często wszystko działa dobrze z każdym z nich. Języki funkcjonalne zwykle używają rekurencji zamiast iteracji. Istnieją lepsze przykłady rekurencji, w których powtarzanie tego samego byłoby niewygodne.
David Thornley,