Prawie każdy artykuł, który mogę znaleźć na temat rekurencji, zawiera przykłady liczb czynnikowych lub Fibonacciego, które są:
- Matematyka
- Bezużyteczne w prawdziwym życiu
Czy są jakieś interesujące przykłady kodu niemathowego do nauczania rekurencji?
Myślę, że algorytmy dziel i zwyciężaj, ale zwykle obejmują one złożone struktury danych.
Odpowiedzi:
Struktury katalogów / plików są najlepszym przykładem zastosowania rekurencji, ponieważ wszyscy je rozumieją, zanim zaczniesz, ale wszystko, co dotyczy struktur przypominających drzewa, zrobi.
źródło
Poszukaj rzeczy, które dotyczą struktur drzew. Drzewo jest stosunkowo łatwe do uchwycenia, a piękno rozwiązania rekurencyjnego staje się widoczne znacznie wcześniej niż w przypadku liniowych struktur danych, takich jak listy.
Rzeczy do przemyślenia:
Wszystkie są powiązane z rzeczywistymi scenariuszami w świecie rzeczywistym i można je wszystkie wykorzystać w aplikacjach o znaczeniu rzeczywistym.
źródło
https://stackoverflow.com/questions/105838/real-world-examples-of-recursion
https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion
https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence
https://stackoverflow.com/questions/126756/examples-of-recursive-functions
źródło
Oto kilka praktycznych problemów, które przychodzą mi na myśl:
źródło
QuickSort byłby pierwszym, który przychodzi mi na myśl. Wyszukiwanie binarne to także problem rekurencyjny. Poza tym istnieją całe klasy problemów, których rozwiązania wypadają prawie za darmo, gdy zaczynasz pracę z rekurencją.
źródło
Sortuj, zdefiniowane rekurencyjnie w Pythonie.
Scal, zdefiniowane rekurencyjnie.
Wyszukiwanie liniowe, zdefiniowane rekurencyjnie.
Wyszukiwanie binarne, zdefiniowane rekurencyjnie.
źródło
W pewnym sensie rekurencja polega na dzieleniu i podbijaniu rozwiązań, czyli zamiataniu przestrzeni problemowej na mniejszą, aby pomóc znaleźć rozwiązanie prostego problemu, a następnie zwykle powracaniu do rekonstrukcji pierwotnego problemu w celu sformułowania właściwej odpowiedzi.
Niektóre przykłady nie wymagające matematyki do nauczania rekurencji (przynajmniej te problemy, które pamiętam z lat uniwersyteckich):
Są to przykłady użycia cofania w celu rozwiązania problemu.
Inne problemy to klasyka w dziedzinie sztucznej inteligencji: korzystanie z głębokiego pierwszego wyszukiwania, wyszukiwanie ścieżek, planowanie.
Wszystkie te problemy wiążą się z jakąś „złożoną” strukturą danych, ale jeśli nie chcesz uczyć matematyki (liczb), twoje wybory mogą być bardziej ograniczone. Yoy może chcieć zacząć uczyć z podstawową strukturą danych, np. Połączoną listą. Na przykład reprezentowanie liczb naturalnych za pomocą listy:
0 = pusta lista 1 = lista z jednym węzłem. 2 = lista z 2 węzłami. ...
następnie zdefiniuj sumę dwóch liczb w odniesieniu do tej struktury danych, jak poniżej: Puste + N = N Węzeł (X) + N = Węzeł (X + N)
źródło
Wieże Hanoi są dobre, aby pomóc w nauce rekurencji.
Istnieje wiele rozwiązań w Internecie w wielu różnych językach.
źródło
Detektor palindromu:
Zacznij od ciągu: „ABCDEEDCBA” Jeśli znaki początkowe i końcowe są równe, powtórz i sprawdź „BCDEEDCB” itp.
źródło
Algorytm wyszukiwania binarnego brzmi jak chcesz.
źródło
W funkcjonalnych językach programowania, gdy nie są dostępne funkcje wyższego rzędu, zamiast pętli imperatywnych używana jest rekurencja w celu uniknięcia stanu zmiennego.
F # jest nieczystym językiem funkcjonalnym, który pozwala na oba style, więc porównam oba tutaj. Poniższe sumuje wszystkie liczby na liście.
Pętla imperatywna ze zmienną zmienną
Pętla rekurencyjna bez stanu zmiennego
Zauważ, że ten rodzaj agregacji jest przechwytywany w funkcji wyższego rzędu
List.fold
i może być zapisany jako,List.fold (+) 0 xlist
a nawet prostszy, z funkcją wygodyList.sum
jako sprawiedliwąList.sum xlist
.źródło
Wykorzystałem rekurencję w grze AI. Pisząc w C ++, skorzystałem z serii około 7 funkcji, które wywołują się w kolejności (pierwsza funkcja ma opcję obejścia wszystkich i zamiast tego wywołuje ciąg 2 dodatkowych funkcji). Ostatnia funkcja w dowolnym łańcuchu ponownie wywoływała pierwszą funkcję, aż pozostała głębokość, którą chciałem przeszukać, osiągnęła wartość 0, w którym to przypadku funkcja końcowa wywołałaby moją funkcję oceny i zwróciła wynik pozycji.
Wiele funkcji pozwoliło mi łatwo rozgałęzić się na podstawie decyzji gracza lub losowych zdarzeń w grze. Korzystałbym z funkcji przekazywania według referencji, gdy tylko mogłem, ponieważ przekazywałem bardzo duże struktury danych, ale ze względu na strukturę gry bardzo trudno było znaleźć opcję „cofnij ruch” podczas wyszukiwania, więc W niektórych funkcjach używałbym wartości przekazywanej, aby zachować oryginalne dane bez zmian. Z tego powodu przejście na podejście oparte na pętli zamiast podejścia rekurencyjnego okazało się zbyt trudne.
Możesz zobaczyć bardzo podstawowy zarys tego rodzaju programu, patrz https://secure.wikimedia.org/wikipedia/en/wiki/Minimax#Pseudocode
źródło
Naprawdę dobrym przykładem z życia w biznesie jest tak zwana „Karta materiałów”. Są to dane reprezentujące wszystkie komponenty, które składają się na gotowy produkt. Na przykład użyjmy roweru. Rower ma kierownicę, koła, ramę itp. I każdy z tych elementów może mieć podzespoły. na przykład koło może mieć szprychy, trzonek zaworu itp. Tak więc zazwyczaj są one reprezentowane w strukturze drzewa.
Teraz, aby wyszukiwać dowolne informacje zbiorcze na temat BOM lub zmieniać elementy w BOM, często uciekasz się do rekurencji.
I przykładowe połączenie rekurencyjne ...
Oczywiście klasa BomPart miałaby znacznie więcej pól. Być może będziesz musiał dowiedzieć się, ile masz plastikowych elementów, ile pracy wymaga zbudowanie kompletnej części itp. Wszystko to jednak wraca do przydatności Rekurencji na strukturze drzewa.
źródło
Relacje rodzinne stanowią dobry przykład, ponieważ wszyscy rozumieją je intuicyjnie:
źródło
||
dlaOR
.Dość bezużyteczna, ale wykazująca rekurencję wewnętrzna dobrze działająca funkcja jest rekurencyjna
strlen()
:Bez matematyki - bardzo prosta funkcja. Oczywiście nie wdrażasz go rekurencyjnie w prawdziwym życiu, ale jest to dobra wersja demonstracyjna rekurencji.
źródło
Innym problemem rekurencyjnym w świecie rzeczywistym, z którym mogą odnosić się studenci, jest zbudowanie własnego robota sieciowego, który pobiera informacje ze strony internetowej i podąża za wszystkimi linkami w tej witrynie (i wszystkimi linkami z tych linków itp.).
źródło
Rozwiązałem problem ze wzorem rycerza (na szachownicy) za pomocą programu rekurencyjnego. Miałeś przesuwać rycerza tak, aby dotykał każdego kwadratu oprócz kilku zaznaczonych kwadratów.
Po prostu:
Można przetestować wiele rodzajów scenariuszy „przyszłościowych”, testując przyszłe możliwości w takim drzewie.
źródło