Rekurencja bez silni, liczb Fibonacciego itp

48

Prawie każdy artykuł, który mogę znaleźć na temat rekurencji, zawiera przykłady liczb czynnikowych lub Fibonacciego, które są:

  1. Matematyka
  2. 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.

lazyCrab
źródło
26
Chociaż twoje pytanie jest całkowicie poprawne, wahałbym się, nazywając numery Fibonacciego bezużytecznym w prawdziwym życiu . To samo dotyczy silni .
Zach L
2
Mały Schemer to cała książka o rekurencji, która nigdy nie używa Faktu ani Fibu. junix-linux-config.googlecode.com/files/…
Eric Wilson
5
@Zach: Mimo to rekurencja jest okropnym sposobem na implementację liczb Fibonacciego z powodu wykładniczego czasu działania.
dan04
2
@ dan04: Recursion to okropny sposób na implementację prawie wszystkiego ze względu na możliwość przepełnienia stosu w większości języków.
R ..
5
@ dan04 chyba że język jest na tyle sprytny, aby wdrożyć ogon optymalizację połączeń jak większość języków funkcyjnych, w którym to przypadku działa dobrze
Zachary K

Odpowiedzi:

107

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.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}
pdr
źródło
1
Dzięki, myślę, że pójdę z systemem plików. Jest to coś konkretnego i może być wykorzystane do wielu przykładów z prawdziwego świata.
synaps
9
Uwaga: komenda unix często wyłącza opcję -r (np. Cp lub rm). -r oznacza rekurencyjny.
deadalnix
7
musisz być tutaj trochę ostrożny, ponieważ w rzeczywistości systemy plików są w rzeczywistości grafem ukierunkowanym, niekoniecznie drzewem, jeśli obsługiwane przez system plików, twarde łącza itp. mogą tworzyć sprzężenia i cykle
jk.
1
@jk: Katalogi nie mogą być połączone na stałe, więc modulo niektóre liście, które mogą pojawić się w więcej niż jednej lokalizacji, i zakładając, że wykluczysz dowiązania symboliczne, rzeczywistymi systemami plików są drzewa.
R ..
1
istnieją inne cechy szczególne niektórych systemów plików dla katalogów, np. punkty ponownej analizy NTFS. Chodzi mi o to, że kod, który nie jest tego specjalnie świadomy, może mieć nieoczekiwane wyniki w rzeczywistych systemach plików
jk.
51

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:

  • systemy plików - są to w zasadzie drzewa; fajnym zadaniem programowania byłoby pobranie wszystkich obrazów .jpg z określonego katalogu i wszystkich jego podkatalogów
  • przodek - biorąc pod uwagę drzewo genealogiczne, znajdź liczbę pokoleń, które musisz przejść, aby znaleźć wspólnego przodka; lub sprawdź, czy dwie osoby w drzewie należą do tego samego pokolenia; lub sprawdź, czy dwie osoby na drzewie mogą legalnie wyjść za mąż (zależy od jurysdykcji :)
  • Dokumenty podobne do HTML - konwertuj między szeregową (tekstową) reprezentacją dokumentu a drzewem DOM; wykonywać operacje na podzbiorach DOM (może nawet zaimplementować podzbiór xpath?); ...

Wszystkie są powiązane z rzeczywistymi scenariuszami w świecie rzeczywistym i można je wszystkie wykorzystać w aplikacjach o znaczeniu rzeczywistym.

tdammers
źródło
Oczywiście należy zauważyć, że ilekroć masz swobodę projektowania własnej struktury drzewa, prawie zawsze lepiej jest zachować wskaźniki / odniesienia do rodzica / następnego rodzeństwa / etc. w węzłach, dzięki czemu można iterować po drzewie bez rekurencji.
R ..
1
Co mają z tym wspólnego wskaźniki? Nawet jeśli masz wskaźniki do pierwszego dziecka, następnego rodzeństwa i rodzica, nadal musisz jakoś przejść przez drzewo, aw niektórych przypadkach rekurencja jest najbardziej wykonalnym sposobem.
tdammers
41

https://stackoverflow.com/questions/105838/real-world-examples-of-recursion

  • modelowanie zakaźnej infekcji
  • generowanie geometrii
  • zarządzanie katalogami
  • sortowanie

https://stackoverflow.com/questions/2085834/how-did-you-practically-use-recursion

  • raytracing
  • szachy
  • parsowanie kodu źródłowego (gramatyka języka)

https://stackoverflow.com/questions/4945128/what-is-a-good-example-of-recursion-other-than-generating-a-fibonacci-sequence

  • Wyszukiwanie BST
  • Wieże Hanoi
  • wyszukiwanie palindromu

https://stackoverflow.com/questions/126756/examples-of-recursive-functions

  • Daje miłą angielską historię, która ilustruje rekurencję na dobranoc.
mskfisher
źródło
10
Chociaż teoretycznie może to odpowiedzieć na pytanie, lepiej byłoby zawrzeć tutaj istotne części tych pytań i odpowiedzi oraz podać odnośniki. Jeśli pytania zostaną kiedykolwiek usunięte z SO, Twoja odpowiedź będzie całkowicie bezużyteczna.
Adam Lear
@ Anna Cóż, użytkownicy nie mogą usunąć swoich pytań, więc jakie jest prawdopodobieństwo, że tak się stanie?
vemv
4
@vemv Usuń głosy, moderatorzy, zasady dotyczące zmiany tematu ... to może się zdarzyć. Tak czy inaczej, bardziej kompletna odpowiedź byłaby lepsza niż wysłanie użytkownika na cztery różne strony od samego początku.
Adam Lear
@Anna: Zgodnie z tym tokiem myślenia każde pytanie zamknięte jako „dokładny duplikat” powinno zawierać odpowiedź z oryginału wklejoną. To pytanie JEST dokładnym duplikatem (pytań na SO), dlaczego powinno być traktowane inaczej niż dokładnie duplikaty pytań na temat programistów?
SF.
1
@SF Jeśli moglibyśmy zamknąć go jako duplikat, zrobilibyśmy to, ale duplikaty między witrynami nie są obsługiwane. Programiści to osobna strona, więc idealnie tutaj odpowiedzi wykorzystałyby SO jako każde inne odniesienie, a nie przekazałyby go całkowicie. Nie różni się niczym od powiedzenia „Twoja odpowiedź znajduje się w tej książce” - technicznie prawdziwe, ale nie można od razu z niego skorzystać bez konsultacji z odnośnikiem.
Adam Lear
23

Oto kilka praktycznych problemów, które przychodzą mi na myśl:

  • Scal sortowanie
  • Wyszukiwanie binarne
  • Przechodzenie, wstawianie i usuwanie na drzewach (w dużej mierze wykorzystywane w aplikacjach bazodanowych)
  • Generator permutacji
  • Sudoku solver (z cofaniem)
  • Sprawdzanie pisowni (ponownie z cofaniem)
  • Analiza składniowa (.eg, program konwertujący prefiks na notację postfiksową)
Daniel Scocco
źródło
11

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

Zachary K.
źródło
3
Wyszukiwanie binarne jest często formułowane jako problem rekurencyjny, ale jego implementacja w trybie rozkazującym jest banalna (i często lepsza).
puszysty
W zależności od języka, którego używasz, kod może, ale nie musi, być jawnie rekurencyjny, imperatywny lub rekurencyjny. Ale wciąż jest to algorytm rekurencyjny, polegający na rozbiciu problemu na coraz mniejsze części, aby dostać się do rozwiązania.
Zachary K
2
@Zachary: Algorytmy, które można zaimplementować za pomocą rekurencji ogona (np. Wyszukiwanie binarne), należą do zasadniczo innej klasy kosmicznej niż te, które wymagają prawdziwej rekurencji (lub własnych struktur stanów o równie kosztownych wymaganiach przestrzennych). Nie wydaje mi się, by korzystna była ich wspólna nauka tak, jakby byli tacy sami.
R ..
8

Sortuj, zdefiniowane rekurencyjnie w Pythonie.

def sort( a ):
    if len(a) == 1: return a
    part1= sort( a[:len(a)//2] )
    part2= sort( a[len(a)//2:] )
    return merge( part1, part2 )

Scal, zdefiniowane rekurencyjnie.

def merge( a, b ):
    if len(b) == 0: return a
    if len(a) == 0: return b
    if a[0] < b[0]:
        return [ a[0] ] + merge(a[1:], b)
    else:
        return [ b[0] ] + merge(a, b[1:]) 

Wyszukiwanie liniowe, zdefiniowane rekurencyjnie.

def find( element, sequence ):
    if len(sequence) == 0: return False
    if element == sequence[0]: return True
    return find( element, sequence[1:] )

Wyszukiwanie binarne, zdefiniowane rekurencyjnie.

def binsearch( element, sequence ):
    if len(sequence) == 0: return False
    mid = len(sequence)//2
    if element < mid: 
        return binsearch( element, sequence[:mid] )
    else:
        return binsearch( element, sequence[mid:] )
S.Lott
źródło
6

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)

Gabriel
źródło
5

Wieże Hanoi są dobre, aby pomóc w nauce rekurencji.

Istnieje wiele rozwiązań w Internecie w wielu różnych językach.

Oded
źródło
3
To jest, moim zdaniem, kolejny zły przykład. Po pierwsze, jest to nierealne; ludzie nie mają z tym problemu. Po drugie, istnieją łatwe nierekurencyjne rozwiązania. (Jednym z nich jest: numerowanie dysków. Nigdy nie przenoś dysku na dysk o tej samej parzystości i nigdy nie cofaj ostatniego wykonanego ruchu. Jeśli będziesz przestrzegać tych dwóch zasad, rozwiążesz układankę optymalnym rozwiązaniem. Nie wymaga rekurencji. )
Eric Lippert,
5

Detektor palindromu:

Zacznij od ciągu: „ABCDEEDCBA” Jeśli znaki początkowe i końcowe są równe, powtórz i sprawdź „BCDEEDCB” itp.

NWS
źródło
6
Jest to również trywialne do rozwiązania bez rekurencji, a IMHO lepiej rozwiązać bez niego.
Blrfl,
3
Uzgodnione, ale PO Konkretnie poproszony o przykłady nauczania przy minimalnym wykorzystaniu struktur danych.
NWS,
5
To nie jest dobry przykład nauczania, jeśli twoi uczniowie mogą natychmiast wymyślić nierekurencyjne rozwiązanie. Dlaczego ktoś miałby zwracać uwagę, gdy twój przykład brzmi „Oto coś trywialnego do zrobienia z pętlą. Teraz pokażę ci trudniejszą drogę bez wyraźnego powodu”.
Przywróć Monikę
5

Algorytm wyszukiwania binarnego brzmi jak chcesz.

Sardathrion
źródło
4

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ą

let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
    sum <- sum + x

Pętla rekurencyjna bez stanu zmiennego

let xlist = [1;2;3;4;5;6;7;8;9;10]
let rec loop sum xlist = 
    match xlist with
    | [] -> sum
    | x::xlist -> loop (sum + x) xlist
let sum = loop 0 xlist

Zauważ, że ten rodzaj agregacji jest przechwytywany w funkcji wyższego rzędu List.foldi może być zapisany jako, List.fold (+) 0 xlista nawet prostszy, z funkcją wygody List.sumjako sprawiedliwą List.sum xlist.

Stephen Swensen
źródło
zasługujesz na więcej punktów niż tylko +1 ode mnie. F # bez rekurencji byłoby bardzo uciążliwe, jest to tym bardziej prawdziwe w przypadku Haskell, który nie ma zapętlonych konstrukcji WYŁĄCZNIE rekurencja!
schoetbi,
3

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

David Stone
źródło
3

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.

    class BomPart
    {
        public string PartNumber { get; set; }
        public string Desription { get; set; }
        public int Quantity { get; set; }
        public bool Plastic { get; set; }
        public List<BomPart> Components = new List<BomPart>();
    }

I przykładowe połączenie rekurencyjne ...

    static int ComponentCount(BomPart part)
    {
        int subCount = 0;
        foreach(BomPart p in part.Components)
            subCount += ComponentCount(p);
        return part.Quantity * Math.Max(1,subCount);

    }

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.

deepee1
źródło
Zestawienie materiałów może być ukierunkowaną ścieżką, a nie drzewem, np. Ta sama specyfikacja śruby może być użyta przez więcej niż jeden element.
Ian
-1

Relacje rodzinne stanowią dobry przykład, ponieważ wszyscy rozumieją je intuicyjnie:

ancestor(joe, me) = (joe == me) 
                    OR ancestor(joe, me.father) 
                    OR ancestor(joe, me.mother);
Caleb
źródło
w jakim języku jest napisany ten kod?
törzsmókus
@ törzsmókus Brak określonego języka. Składnia jest dość blisko do C, obj-C, C ++, Java i wielu innych językach, ale jeśli chcesz prawdziwy kod może trzeba zastąpić odpowiedniego operatora, takie jak ||dla OR.
Caleb
-1

Dość bezużyteczna, ale wykazująca rekurencję wewnętrzna dobrze działająca funkcja jest rekurencyjna strlen():

size_t strlen( const char* str )
{
    if( *str == 0 ) {
       return 0;
    }
    return 1 + strlen( str + 1 );
}

Bez matematyki - bardzo prosta funkcja. Oczywiście nie wdrażasz go rekurencyjnie w prawdziwym życiu, ale jest to dobra wersja demonstracyjna rekurencji.

sharptooth
źródło
-2

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

GregW
źródło
2
Zasadniczo lepiej jest to obsługiwane przez kolejkę procesów w przeciwieństwie do rekurencji w tradycyjnym sensie.
puszysty
-2

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:

mark your "Current" square
gather a list of free squares that are valid moves
are there no valid moves?
    are all squares marked?
        you win!
for each free square
    recurse!
clear the mark on your current square.
return.    

Można przetestować wiele rodzajów scenariuszy „przyszłościowych”, testując przyszłe możliwości w takim drzewie.

Bill K.
źródło