Zasoby do lepszego zrozumienia rekurencji? [Zamknięte]

Wiem, co to jest rekurencja (kiedy patten pojawia się ponownie w sobie, zazwyczaj funkcja, która wywołuje się na jednej ze swoich linii, po warunku wybicia ... prawda?), I mogę zrozumieć funkcje rekurencyjne, jeśli dokładnie je przestudiuję. Mój problem polega na tym, że kiedy widzę nowe przykłady, zawsze jestem początkowo zdezorientowany. Jeśli widzę pętlę lub odwzorowanie, zipowanie, zagnieżdżanie, wywoływanie polimorficzne itd., Wiem, co się dzieje, patrząc na nie. Kiedy widzę kod rekurencyjny, moim procesem myślowym jest zazwyczaj „wtf, prawda?” po którym następuje „och, to rekurencyjne”, po czym „Myślę, że musi działać, jeśli mówią, że działa”.

Czy masz jakieś wskazówki / plany / zasoby dotyczące rozwijania umiejętności w tym obszarze? Rekursja jest rodzajem dziwnej koncepcji, więc myślę, że sposób rozwiązania tego problemu może być równie dziwny i nieoczywisty.

Zacznij od czegoś prostego i prześledź to ołówkiem i papierem. Serio Dobrym miejscem do rozpoczęcia są algorytmy przechodzenia przez drzewa, ponieważ są one znacznie łatwiejsze do obsługi przy użyciu rekurencji niż zwykłej iteracji. Nie musi to być skomplikowany przykład, ale coś, co jest proste i można z nim pracować.

Tak, to dziwne i czasem sprzeczne z intuicją, ale kiedy kliknie, powie „Eureka!” będziesz się zastanawiać, jak wcześniej tego nie rozumiałeś! ;) Zasugerowałem drzewa, ponieważ są one (IMO) najłatwiejszą strukturą do zrozumienia w rekurencji i są łatwe w użyciu za pomocą ołówka i papieru. ;)

Zdecydowanie polecam Scheme, korzystając z książki The Little Lisper. Kiedy skończysz z nim, to będzie zrozumieć rekurencję w głębi. Prawie gwarantowane.

Zdecydowanie sugeruję SICP. Warto też zapoznać się z filmami wprowadzającymi autorów tutaj ; niesamowicie otwierają umysł.

Inną drogą, nie tak ściśle związaną z programowaniem, jest czytanie Gödel, Escher, Bach: Eternal Golden Braid autorstwa Hofstadtera. Po przejściu przez nią rekurencja będzie wyglądać tak naturalnie, jak arytmetyka. Będziesz także przekonany, że P = nP i będziesz chciał budować maszyny myślące - ale to efekt uboczny, który jest tak niewielki w porównaniu do korzyści.

Zasadniczo sprowadza się to do ćwiczenia ... Weź ogólne problemy (sortowanie, wyszukiwanie, problemy matematyczne itp.) I sprawdź, czy widzisz sposób, w jaki można rozwiązać te problemy, jeśli zastosujesz jedną funkcję kilka razy.

Na przykład szybkie sortowanie działa w ten sposób, że przenosi element z listy na dwie połowy, a następnie stosuje się ponownie do każdej z tych połówek. Kiedy następuje wstępne sortowanie, nie martwi się o posortowanie dwóch połówek w tym momencie. Raczej bierze się element obrotowy i umieszcza wszystkie elementy mniejsze niż ten element po jednej stronie i wszystkie elementy większe lub równe po drugiej stronie. Czy ma to sens, jak może rekurencyjnie nazywać się w tym momencie, aby posortować dwie nowe mniejsze listy? To także listy. Po prostu mniejszy. Ale nadal trzeba je posortować.

Siłą stojącą za rekurencją jest pojęcie dziel i zwyciężaj. Podziel problem wielokrotnie na mniejsze problemy, które z natury są identyczne, ale tylko mniejsze. Jeśli zrobisz to wystarczająco, ostatecznie dojdziesz do punktu, w którym jedyny pozostały element jest już rozwiązany, po prostu cofniesz się z pętli i problem zostanie rozwiązany. Przestudiuj wspomniane przykłady , dopóki ich nie zrozumiesz . Może to chwilę potrwać, ale w końcu będzie łatwiej. Następnie spróbuj podjąć inne problemy i użyj funkcji rekurencyjnej, aby je rozwiązać! Powodzenia!

EDYCJA: Muszę również dodać, że kluczowym elementem rekurencji jest gwarantowana zdolność funkcji do zatrzymania się. Oznacza to, że załamanie pierwotnego problemu musi być coraz mniejsze i ostatecznie musi istnieć gwarantowany punkt zatrzymania (punkt, w którym nowy problem podrzędny jest albo do rozwiązania, albo już rozwiązany).

Osobiście uważam, że najlepiej jest ćwiczyć.

Nauczyłem się rekurencji z LOGO. Możesz użyć LISP. W tych językach rekursja jest naturalna. W przeciwnym razie możesz to porównać do badania pakietów matematycznych i serii, w których wyrażasz, co dalej, na podstawie tego, co było wcześniej, tj. U (n + 1) = f (u (n)), lub bardziej złożonej serii, w której masz wiele zmiennych i wiele zależności, np. u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Sugeruję więc, abyś znalazł (w ich wyrażeniu) standardowe „problemy” rekurencyjne i spróbował wdrożyć je w wybranym języku. Praktyka pomoże ci nauczyć się myśleć, czytać i wyrażać te „problemy”. Zauważ, że często niektóre z tych problemów można wyrazić poprzez iterację, ale rekurencja może być bardziej eleganckim sposobem ich rozwiązania. Jednym z nich jest obliczanie liczb silni.

Graficzne „problemy”, które widzę, ułatwiają dostrzeżenie. Więc spójrz na płatki Kocha, Fibonacciego, smoczą krzywą i ogólnie fraktale. Ale spójrz także na algorytm szybkiego sortowania ...

Musisz załamać kilka programów (niekończące się pętle, niepewne użycie nieskończonych zasobów) i źle obchodzić warunki końcowe (aby uzyskać nieoczekiwane wyniki), zanim zaczniesz wszystko robić. I nawet gdy go dostaniesz, nadal będziesz popełnił te błędy, tylko rzadziej.

Struktura i interpretacja programów komputerowych

Jest książka używana do nauki, nie tylko rekurencja, ale w ogóle programowania na różnych uniwersytetach. Jest to jedna z tych fundamentalnych książek, która dostarcza więcej informacji, im więcej zdobędziesz doświadczenia i tym więcej go przeczytasz.

Tak jak lubię SICP i Gödela, Eschera, Bacha: wieczny złoty warkocz, LISP Touretzky'ego : Delikatne wprowadzenie do obliczeń symbolicznych również dobrze sprawdza się we wprowadzaniu rekurencji.

Podstawowa koncepcja jest następująca: po pierwsze, musisz wiedzieć, kiedy funkcja rekurencyjna jest zakończona, aby mogła zwrócić wynik. Następnie musisz wiedzieć, jak wziąć niedokończoną sprawę i sprowadzić ją do czegoś, co możesz powtórzyć. W tradycyjnym przykładzie silnia (N) skończyłeś, gdy N <= 1, a niedokończony przypadek to N * silnia (N-1).

Dla o wiele bardziej brzydkiego przykładu istnieje funkcja Ackermanna A (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.

Proponuję bawić się językami funkcjonalnymi w stylu ML, takimi jak OCaml lub Haskell. Odkryłem, że składnia dopasowywania wzorców naprawdę pomogła mi zrozumieć nawet stosunkowo skomplikowane funkcje rekurencyjne, z pewnością znacznie lepsze niż Scheme ifi condinstrukcje. (Nauczyłem się Haskell i Scheme w tym samym czasie.)

Oto prosty przykład kontrastu:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

i z dopasowaniem wzoru:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Ten przykład tak naprawdę nie oddaje różnicy - nigdy nie miałem problemów z żadną wersją funkcji. Aby zilustrować, jak wyglądają te dwie opcje. Kiedy dojdziesz do znacznie bardziej złożonych funkcji, używając rzeczy takich jak listy i drzewa, różnica staje się znacznie wyraźniejsza.

Szczególnie polecam Haskell, ponieważ jest to prosty język z bardzo ładną składnią. Znacznie ułatwia także pracę z bardziej zaawansowanymi pomysłami, takimi jak corecursion :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(Nie zrozumiesz powyższego kodu, dopóki nie zagrasz trochę z Haskellem, ale bądź pewien, że jest to w zasadzie magiczne: P.) Pewnie, że możesz zrobić to samo ze strumieniami w Schemacie, ale w Haskell jest to o wiele bardziej naturalne.

Nie ma go już w druku, ale jeśli go znajdziesz, „Recursive Algorytmy” Richarda Lorentza dotyczy wyłącznie rekurencji. Obejmuje podstawy rekurencji, a także określone algorytmy rekurencyjne.

Przykłady są w języku Pascal, ale nie są tak duże, że wybór języka jest uciążliwy.