Mówiąc wprost, czym jest rekurencja?

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

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

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:

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

Trudniej

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

• W Fibonacciego Liczby,
• Największy wspólny dzielnik ,
• Problem 8-królowych ,
• Gra Towers of Hanoi ,
• A jeśli masz środowisko graficzne (lub możesz udostępnić kody pośredniczące dla niego lub dla danych wyjściowych terminala lub mogą one już to zarządzać), na przykład:
  • Fraktal Koch's Snow Flake ,
  • Trójkąt Sierpińskiego .
• Aby uzyskać praktyczne przykłady, rozważ napisanie:
  • algorytm przejścia drzewa,
  • prosty parser wyrażeń matematycznych,
  • gra trałowiec.

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 :

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 .

Wywołanie funkcji z tej samej funkcji.

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.

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.

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?

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.

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.

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.

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

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.

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.

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.

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

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 .

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.

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

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

• Wieża Hanoi
• Baguenaudier

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