Rekurencja bez silni, liczb Fibonacciego itp

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.

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;
}

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.

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.

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

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

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:] )

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

• Wieże Hanoi
• Osiem królowych

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)

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

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

Detektor palindromu:

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

Algorytm wyszukiwania binarnego brzmi jak chcesz.

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.

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

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.

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

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.

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

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.