Rekurencja - czy to „dziel i rządź”, czy „ponowne użycie kodu”

11

Rekurencja - jak wszyscy wiemy - jest jednym z tych problemów - że otulenie głowy wydaje się osiągnięciem „kamienia milowego” w podróży programistycznej.

Ale jeśli chodzi o faktyczne wykorzystanie go w rzeczywistych problemach - znajomość mechaniki rekurencji NIE wystarcza - należy także zrozumieć naturę problemów, w których rekurencja jest najbardziej odpowiednim rozwiązaniem.

Moje pytanie brzmi więc ...

  • jakie są „wzorce problemów”, które wymagają rozwiązania rekurencji
  • jest rekursją formą strategii „dziel i rządź” lub formą „ponownego wykorzystania kodu” - lub jest wzorzec projektowy sam w sobie
  • czy możesz podać nam przykład rzeczywistego problemu, w którym rekurencja przychodzi na myśl jako natychmiastowe rozwiązanie

-- AKTUALIZACJA --

wiele odpowiedzi odnosi się do „prawdziwych problemów”, takich jak przemierzanie drzewa, silnia itp. Wolałbym „PRAWDZIWE prawdziwe problemy” - dam wam przykład ...

Mieliśmy DUŻĄ porcję tekstu (około 30 MB tekstu jako połączonej listy structs) i musieliśmy stworzyć jego indeks do przeszukiwania pełnego tekstu. Musieliśmy zachować cały indeks w pamięci i ponownie indeksować tekst co 10 minut.

Co 10 minut porównujemy cały tekst (dwie połączone listy, linia po linii) z nowo wygenerowanym fragmentem tekstu - aby zobaczyć, który wiersz został zmieniony - a następnie ponownie indeksujemy tylko ten wiersz - w ten sposób moglibyśmy uniknąć konieczności ponownego indeksowania CAŁEGO tekstu. Pamiętaj - musieliśmy znaleźć punkty różnic między dwiema połączonymi listami o wielkości 30 MB.

Jeden z moich kolegów wymyślił fantastyczny program, który wykorzystywał rekurencję HEAVY do porównywania linii - a następnie zbierał pozycje, w których uchwyty różniły się w tablicy - tak, wiem, że to brzmi zagadkowo - jak tu może pomóc rekurencja - ale to zrobiło.

Chodzi o to - jak mógł zobaczyć, że problem ten można rozwiązać mądrze przy użyciu rekurencji?

recursion treecoder
źródło
Czy 30 MB jest naprawdę duże w dzisiejszych czasach, gdy większość komputerów ma GB pamięci RAM i TB miejsca na dysku twardym?
JB King
30 MB może NIE być duże - ale biorąc pod uwagę rodzaj struktury danych, w której nasz tekst był wciśnięty - był to naprawdę DUŻY fragment tekstu do PROCESU - i DIFF.
treecoder
3
Czy „przechodzenie przez strukturę folderów” nie jest wystarczająco PRAWDZIWE? I całkowicie nie widzę w twoim przykładzie, jak rekurencja powinna być tutaj nieintuicyjna i dlaczego jej użycie powinno być szczególnie godne uwagi. Twój kolega zaprojektował algorytm rekurencyjny, tak jak każdy inny algorytm. Równie dobrze możesz zapytać, w jaki sposób Hoare wpadł na pomysł rozwiązania problemu sortowania rekurencyjnie.
Konrad Rudolph
2
Czy mam rację, myśląc, że miałeś na myśli „ponowne użycie kodu” bardziej niż „wykonywanie tej samej serii operacji nieokreśloną liczbę razy”? Jest to przeciwieństwo „ponownego użycia kodu” w sensie pisania kodu ogólnego do użytku w innym miejscu.
Andy Hunt
4
Ale przechodzenie przez drzewa to „PRAWDZIWY prawdziwy problem”, z którym wiele osób spotyka się prawie codziennie.
Falcon,

Odpowiedzi:

16
  • jakie są „wzorce problemów”, które wymagają rozwiązania rekurencji

Nie powiedziałbym, że istnieje coś takiego jak wzorzec problemowy dla użycia rekurencji. Każda funkcja, która może być zaimplementowana za pomocą rekurencji, może być również zaimplementowana iteracyjnie, często przez wypychanie i otwieranie stosu.

To kwestia ekspresji, a także wydajności. Algorytmy iteracyjne często mają lepszą wydajność i łatwiej je zoptymalizować. Jednak algorytmy rekurencyjne korzystają z wyraźniejszego wyrażenia i dlatego często są łatwiejsze do odczytania, zrozumienia i wdrożenia.

Niektórych rzeczy nawet nie da się wyrazić bez rekurencji, na przykład nieskończonych list. Tak zwane języki funkcjonalne w dużej mierze polegają na rekurencji, ponieważ jest to ich naturalny sposób wyrażania. Mówi się: „Programowanie rekurencyjne to prawidłowe funkcjonowanie programowania”.

  • jest rekursją formą strategii „dziel i rządź” lub formą „ponownego wykorzystania kodu” - lub jest wzorzec projektowy sam w sobie

Nie nazwałbym tego wzorem. To kwestia ekspresji. Czasami wyrażenie rekurencyjne jest po prostu mocniejsze i bardziej ekspresyjne, a zatem prowadzi do lepszego i czystszego kodu.

  • czy możesz podać nam przykład rzeczywistego problemu, w którym rekurencja przychodzi na myśl jako natychmiastowe rozwiązanie

Wszystko, co musi przejść przez drzewa, zostanie poprawnie wyrażone przez algorytm rekurencyjny.

Sokół
źródło
7
„Każda funkcja, która może być zaimplementowana za pomocą rekurencji, może być również zaimplementowana iteracyjnie, często przez wypychanie i otwieranie stosu”. W końcu w językach, które wykorzystują pamięć opartą na stosie, już wypychasz i wstawiasz dane funkcji na stosie i poza nim, gdy używasz rekurencji.
JAB
Tylko jeśli skompilujesz lub zinterpretujesz język na maszynie ;-) Ponadto, z bardzo wysokiego punktu widzenia, wyrażenie i język są całkowicie niezależne od maszyny i sprzętu oraz systemu operacyjnego, więc niekoniecznie jest stos.
Falcon
Ach, tak, masz absolutną rację. Powinienem był powiedzieć „w implementacjach języków / kompilatorów językowych wykorzystujących pamięć stosową”.
JAB,
Ogólnie rzecz biorąc, też masz rację. Nie chciałem wyglądać na głupiego.
Falcon
2
Listy nieskończone mogą być wyrażane bez rekurencji, przynajmniej bez rekurencyjnej implementacji. Generatory Pythona mogą to zrobić, podobnie jak generatory w Icon, od którego wydaje się, że Python zapożyczył ten pomysł. Wierzę, że F # może zrobić tę sztuczkę, choć nie jestem pewien. Zasadniczo generatory są szczególnym przypadkiem wspólnych procedur (takich jak wielozadaniowość kooperacyjna), które dobrze nadają się do implementacji leniwych list. Za każdym razem, gdy generator „daje” wynik, wywołujący odzyskuje kontrolę, a generator pozostaje bezczynny do momentu zażądania następnego wyniku.
Steve314,
8

jest rekursją formą strategii „dziel i rządź” lub formą „ponownego wykorzystania kodu” - lub jest wzorzec projektowy sam w sobie

Ani. Dziel i rządź używa rekurencji. Ale rekurencja niekoniecznie dzieli i zwycięża, ponieważ ta ostatnia oznacza podzielenie problemu na dwie (lub więcej) części i rozwiązanie każdej z nich symetrycznie. W rekursji tego nie robisz.

Ponowne użycie kodu jest całkowicie niezwiązane, a wzorzec projektowy wchodzi w grę na znacznie wyższym poziomie. Na przykład nawet dzielenie i podbijanie (również wzorzec wyższego poziomu niż rekurencja) nadal nie jest uważane za wzorzec projektowy - jest raczej wzorcem algorytmicznym .

czy możesz podać nam przykład rzeczywistego problemu, w którym rekurencja przychodzi na myśl jako natychmiastowe rozwiązanie

Przechodzenie przez drzewo. Lub bardziej ogólnie przejście przez wykres. Dotyczy to w szczególności przejścia przez strukturę folderów.

I oczywiście wszystko, co wykorzystuje program dziel i zwyciężaj lub programowanie dynamiczne, ponieważ oba są naturalnie wyrażane w kategoriach rekurencji.

Konrad Rudolph
źródło
Programowanie dynamiczne nie zawsze jest naturalnie wyrażane jako rekurencja. W rzeczywistości programowanie dynamiczne ściśle odnosi się do podejść tabelarycznych - z wyłączeniem zapamiętywania. Wydaje się, że opinie na ten temat różnią się, ale „programowanie” w „programowaniu dynamicznym” jest w rzeczywistości terminem matematycznym, odnoszącym się do podejść tabelarycznych (trochę ciekawostek, które podniosłem z kursu algorytmów MIT opensourceware). Tak więc ściśle, programowanie dynamiczne wykorzystuje optymalną podkonstrukcję, wykorzystując to, co często najłatwiej wyrazić w postaci prostej pętli. Zapamiętywanie znacznie częściej oznacza rekurencję, ale niekoniecznie.
Steve314,
1
@ Steve314 Zgadzam się, że praktyczna implementacja DP (czy to w programie komputerowym, czy ręcznie) rzadko korzysta z rekurencji. Ale pomysł jest z natury oparty na relacji powtarzalności - która jest tylko formułą rekurencyjną! - i skrzynka podstawowa.
Konrad Rudolph
Zgadzam się, że „optymalna podbudowa” (optymalne rozwiązanie ma optymalne rozwiązania częściowe) jest pomysłem rekurencyjnym. Jest to matematyczne / informatyczne spojrzenie na rekurencję, niezwiązane bezpośrednio z implementacją - ale rola rekurencji w informatyce jest ważnym punktem do podkreślenia. Niewiele algorytmów (i prawdopodobnie nie ma wzorców projektowych) są ważnymi narzędziami w informatyce - większość z nich to raczej przedmioty do nauki, a nie narzędzia do badania czegoś innego.
Steve314,
4 
what are the "problem patterns" that call for the solution of recursion

Wywodząc się z samopodobieństwa fraktali, powiedziałbym, że równość lub tożsamość (lub jak się to nazywa) jest typowym wzorem problemu dla rekurencji. Tj. Problem można podzielić na podproblemy, które mają tę samą strukturę co problem główny.

We wspomnianym przejściu do drzewa każde pod-drzewo samo w sobie jest pełnym drzewem, podobnie jak główne drzewo, a główne drzewo może być poddrzewem w innym drzewie.

Sądzę więc, że twój kolega odkrył właściwości równości twojego problemu z indeksowaniem. Albo odwrócił się i przekształcił problem w samowystarczalną reprezentację.

Bezpieczne
źródło
1
+1 za „problem można podzielić na podproblemy, które mają tę samą strukturę co główny problem”
treecoder
+1 i parafraza: gdzie rozwiązanie problemu dotyczy warstw potomnych. Moim prawdziwym przykładem jest znalezienie opłat za karty kredytowe, które przyczyniają się do „partii”. Oprogramowanie księgowe będzie miało indywidualne opłaty i partię wpłaty na konto czekowe. Moja sprawa może stać się tutaj pytaniem, ponieważ przepełnienie stosu nie było zbyt ostre. stackoverflow.com/questions/14719806
Chris K
3

Cóż, rekurencję można łatwo zrozumieć, jeśli spróbujemy przekształcić imperatywne pętle w funkcje funkcjonalne. W każdym razie spróbujmy odpowiedzieć na wszystkie pytania:

jakie są „wzorce problemów”, które wymagają rozwiązania rekurencji

Jeśli masz strukturę lub algorytm przypominający drzewo, potrzebujesz rekurencji. Jeśli twój imperatywny kod dotyczy stosu, będziesz potrzebować rekurencji. Jeśli określony krok w algorytmie zależy od poprzednich kroków (pętli), potrzebujesz rekurencji. Potrzebę tutaj należy interpretować jako możliwą do wykorzystania.

jest rekursją formą strategii „dziel i rządź” lub formą „ponownego wykorzystania kodu” - lub jest wzorzec projektowy sam w sobie

Żaden. Dziel i rządź używa rekurencji, ale może być implementowane za pomocą stosów. Ponowne użycie kodu odnosi się do czegoś innego. Wzory projektowe są bardziej skomplikowane niż zwykła rekurencja.

czy możesz podać nam przykład rzeczywistego problemu, w którym rekurencja przychodzi na myśl jako natychmiastowe rozwiązanie

Analiza składniowa i wszystko, co dotyczy struktur drzewiastych. Nawet ukryte struktury drzew.

Mihai Maruseac
źródło
3

Jeśli istnieje sposób na uproszczenie go tak, aby był łatwy, może to być wskazówka, że ​​rekurencja może zadziałać. Możesz podjąć sortowanie i poszukiwanie przykładów, w których istnieją rozwiązania rekurencyjne, takie jak Merge Sort i Binary Search .

Należy pamiętać o tym, że niektóre problemy można słabo rozwiązać za pomocą rekurencji jak czynnik.

Jeśli chodzi o przykład z prawdziwego świata, w którym użyłbym rekurencji, wyszukiwanie książki z półki na książki można zrobić dość łatwo w sposób rekurencyjny. Patrzę tylko na książkę i jeśli nie jest to, czego chcę, przechodzę do następnej. Zatrzymuję się, gdy albo znajduję książkę, albo trafiam na koniec rzędu. Zapętlenie sprawdzania książki i przejścia do następnej można wykonać rekurencyjnie. Być może jest to zbyt prawdziwy przykład.

JB King
źródło
2

jakie są „wzorce problemów”, które wymagają rozwiązania rekurencji

Mówiąc bardzo ogólnie, rekurencja jest wymagana, gdy rozwiązujesz problem, w którym f (x) = f (g (x)) . Jeśli nie masz nic przeciwko nieskończonej rekurencji, g (x) nie powinno oceniać na x .

jest rekursją formą strategii „dziel i rządź” lub formą „ponownego wykorzystania kodu” - lub jest wzorzec projektowy sam w sobie

Żadne z powyższych. To tylko sposób na powtarzanie tego samego, czasami w oparciu o zmiany na wejściu. Pomysł był o wiele dłuższy niż wzorce projektowe, ponowne użycie kodu, a nawet komputery.

czy możesz podać nam przykład rzeczywistego problemu, w którym rekurencja przychodzi na myśl jako natychmiastowe rozwiązanie

Czynniki, sekwencję Fibonacciego, przechodzenie przez drzewa i wiele innych problemów można rozwiązać za pomocą recusrionu. Rekurencja w znaczeniu funkcji wywołującej samą siebie niekoniecznie jest najlepszym sposobem na zaimplementowanie tego rodzaju rzeczy; istnieją inne sposoby osiągnięcia tego samego efektu (np. stos i pętla), które mogą być bardziej pożądane.

Blrfl
źródło
-1

Kiedy piszesz algorytm rekurencyjny, zwykle tłumaczysz rekurencyjną definicję problemu na kod. Wtedy nawet nie musisz wiedzieć, jak zostanie to wykonane.

Tak dzieje się w programowaniu funkcjonalnym. W rzeczywistości określasz, co (definicja), a nie jak . Innymi słowy, definiujesz podstawę, a następnie definiujesz swój problem w ramach podproblemu.

Rozważmy na przykład Factorialalgorytm

  • Zdefiniuj podstawę: silnia (1) = 1;
  • Zdefiniuj silnia n: silnia (n) = n * silnia (n-1);

Następnie, gdy napotkasz problem, powinieneś pomyśleć, czy możesz go zdefiniować rekurencyjnie, czy nie, jeśli możesz zdefiniować go rekurencyjnie, prawie go rozwiązałeś.

Jednak żadna funkcja rekurencyjna nie powinna być definicją rekurencyjną. Możesz zdefiniować podstawę i powiązać (zdefiniować) rozwiązanie głównego problemu z rozwiązaniem (definicją) podproblemów. Ale dla tej relacji może być potrzebna procedura.

Przykładem MergeSort, w którym mergemoże być konieczne procedury odnoszą się do definicji lub roztwór sortowania całą tablicę do sortowania tablic podrzędnych.

Ahmad
źródło