Zasoby do lepszego zrozumienia rekurencji? [Zamknięte]

13

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.

Andrew M.
źródło
28
Aby zrozumieć rekurencję, musisz najpierw zrozumieć rekurencję.
Andreas Johansson,
1
„Kot w kapeluszu wraca” dr Seussa, może to nie być całkiem przydatne, ale rekursywne wołanie kota pozbywa się tej irytującej plamy. :-) Ma również tę zaletę, że jest bardzo szybki do przeczytania!
DKnight
2
Ćwicz, ćwicz, ćwicz.
David Thornley,
20
Odpowiedziałem już na to pytanie: programmers.stackexchange.com/questions/57243/…
Graham Borland,
3
@Graham Borland: To przykład nieskończonej rekurencji. W większości programów brak przypadku podstawowego zwykle powoduje przepełnienie stosu lub błąd braku pamięci. Dla użytkowników witryny może to powodować zamieszanie. ;)
FrustratedWithFormsDesigner

Odpowiedzi:

10

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

FrustratedWithFormsDesigner
źródło
1
+1 to jest sposób, w jaki to myślałem. np. jeśli używasz OO, stwórz klasy z relacją rodzicielską, a następnie spróbuj stworzyć funkcję / metodę, która sprawdzi, czy obiekt ma określonego przodka.
Alb
5

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.

jcomeau_ictx
źródło
1
+1 Ta książka naprawdę mi to zrobiła. Ale nazwa została zmieniona na „Mały Schemer”
mike30
4

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.

cbrandolino
źródło
GEB i tak warto przeczytać; nawet jeśli niektóre rzeczy, o których mówi, są nieco przestarzałe (w ciągu ostatnich 40 lat poczyniono pewne postępy w podstawowych badaniach nad CS), podstawowe zrozumienie nie jest.
Donal Fellows
2

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

Kenneth
źródło
Tak, myślę, że widziałem już szybkie wyjaśnienie sortowania, mogę sobie wyobrazić, jak to działa z twojego przypomnienia powyżej. Jak ekspresyjna / elastyczna jest rekurencja - czy większość problemów można przekształcić w podejście rekurencyjne (nawet jeśli nie jest optymalne)? Widziałem ludzi odpowiadających na łamigłówki kodujące w sieci, z którymi większość ludzi radziła sobie proceduralnie, tak jakby mogli skorzystać z rekurencji, kiedy tylko chcieli. Czytałem też raz, jak sądzę, że niektóre języki zależą lub rekurencję w celu zastąpienia konstrukcji pętli. I wspominasz o gwarantowanym punkcie zatrzymania. Czuję, że jedna z tych rzeczy może być kluczem.
Andrew M,
Dobrym prostym problemem początkowym do samodzielnego stworzenia byłoby napisanie programu rekurencyjnego, który znajdzie silnię liczby.
Kenneth
Każda struktura zapętlona może zostać umieszczona w strukturze rekurencyjnej. Każda struktura rekurencyjna może zostać umieszczona w strukturze zapętlonej ... mniej więcej. Nauczenie się, kiedy i kiedy nie należy korzystać z rekurencji, wymaga czasu i praktyki, ponieważ trzeba pamiętać, że podczas korzystania z rekurencji istnieje wiele kosztów ogólnych w zakresie zasobów używanych na poziomie sprzętowym.
Kenneth
Na przykład widziałem, że wykonalne jest tworzenie pętlowej struktury, która wykonuje szybkie sortowanie ... ALE to pewne, bo do cholery byłby to królewski ból i zależnie od tego, jak to zostało zrobione, może w końcu użyć więcej zasobów systemowych niż funkcji rekurencyjnej dla dużych tablic.
Kenneth
oto moja próba silnia. żeby być uczciwym, widziałem to już wcześniej i chociaż napisałem to od zera, a nie pamięci, prawdopodobnie jest to wciąż łatwiejsze niż byłoby. Próbowałem tego w JS, ale wystąpił błąd analizy, ale działa w Pythonie def factorial(number): """return factorial of number""" if number == 0: return 0 elif number == 1: return 1 else: return number * factorial(number - 1)
Andrew M
2

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.

asoundmove
źródło
2

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.

dietbuddha
źródło
0

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.
John R. Strohm
źródło
0

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.

Tikhon Jelvis
źródło
0

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.

Wayne Conrad
źródło