Przykład rekurencji w świecie rzeczywistym

Może coś związanego ze strukturą katalogów w systemie plików. Rekurencyjnie znajdowanie plików, usuwanie plików, tworzenie katalogów itp.

Oto implementacja Javy, która rekurencyjnie drukuje zawartość katalogu i jego podkatalogów.

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Quicksort, merge sort i większość innych N-logów N sortów.

Przykład Matta Dillarda jest dobry. Ogólnie rzecz biorąc, każde chodzenie po drzewie może być obsługiwane przez rekursję bardzo łatwo. Na przykład kompilowanie drzew parsowania, poruszanie się po XML lub HTML, itp.

Rekurencja jest często używana w implementacjach algorytmu Backtrackingu . Jeśli chodzi o" prawdziwe " zastosowanie tego, co powiesz na Sudoku solver?

Rekurencja jest odpowiednia, gdy problem można rozwiązać dzieląc go na pod-problemy, które mogą użyć tego samego algorytmu do ich rozwiązania. Algorytmy na drzewach i posortowanych listach są naturalnym dopasowaniem. Wiele problemów w geometrii obliczeniowej (i grach 3D) można rozwiązać rekurencyjnie za pomocą binary space partitioning (BSP) trees, fat subdivisions , lub innych sposobów dzielenia świata na części.

Rekurencja jest również odpowiednia, gdy próbujesz zagwarantować poprawność algorytmu. Biorąc pod uwagę funkcję, która pobiera niezmienne wejścia i zwraca wynik, który jest kombinacją rekurencyjnych i nie rekurencyjnych wywołań na wejściach, zwykle łatwo jest udowodnić, że funkcja jest poprawna (lub nie) za pomocą indukcji matematycznej. Często trudno jest to zrobić z funkcją iteracyjną lub z wejściami, które mogą mutować. Może to być przydatne w przypadku obliczeń finansowych i innych aplikacji, w których poprawność jest bardzo ważna.

Z pewnością wiele kompilatorów używa mocno rekurencji. Języki komputerowe same w sobie są z natury rekurencyjne (np. można osadzać wyrażenia " if "wewnątrz innych wyrażeń" if " itp.).

Wyłączenie / ustawienie Tylko do odczytu dla wszystkich kontrolek dla dzieci w kontrolce kontenera. Musiałem to zrobić, ponieważ niektóre kontrolki dla dzieci były kontenerami.

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

Słynny cykl Eval / Apply z SICP

Oto definicja eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

Oto definicja zastosuj:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

Oto definicja sekwencji eval:

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval -> apply -> eval-sequence -> eval

Rekurencja jest używana w takich rzeczach jak drzewa BSP do wykrywania kolizji w tworzeniu gier (i innych podobnych obszarach).

Ludzie często sortują stosy dokumentów metodą rekurencyjną. Na przykład wyobraź sobie, że sortujesz 100 dokumentów z nazwami na nich. Najpierw umieść dokumenty w stosach według pierwszej litery, a następnie posortuj każdy stos.

Wyszukiwanie słów w słowniku jest często wykonywane metodą wyszukiwania binarnego, która jest rekurencyjna.

W organizacjach szefowie często wydają polecenia kierownikom działów, którzy z kolei wydają polecenia kierownikom itd.

Parsery i kompilatory mogą być pisane metodą rekurencyjną. Nie jest to najlepszy sposób, ponieważ narzędzia takie jak lex/yacc generują szybsze i bardziej wydajne parsery, ale koncepcyjnie proste i łatwe do wdrożenia, więc pozostają powszechne.

Wymagania realne dostałem niedawno:

Wymóg A: zaimplementuj tę funkcję po dokładnym zrozumieniu wymogu A.

Rekurencja jest stosowana do problemów (sytuacji), w których można ją podzielić(zmniejszyć) na mniejsze części, a każda część (y) wygląda podobnie do pierwotnego problemu.

Dobre przykłady, gdzie rzeczy, które zawierają mniejsze części podobne do siebie są:

• struktura drzewa (gałąź jest jak drzewo)
• listy (część listy jest nadal listą)
• pojemniki (rosyjskie lalki)
• sekwencje (część sekwencji wygląda jak następna)
• grupy obiektów (a podgrupa jest nadal grupą obiektów)

Rekurencja jest techniką, która rozbija problem na mniejsze i mniejsze kawałki, aż jeden z tych kawałków stanie się wystarczająco mały, aby stać się bułką z masłem. Oczywiście, po ich rozbiciu, musisz" zszyć " wyniki z powrotem w odpowiedniej kolejności, aby stworzyć całkowite rozwiązanie pierwotnego problemu.

Niektóre algorytmy sortowania rekurencyjnego, algorytmy chodzenia po drzewach, algorytmy mapowania/zmniejszania, dzielenia i zdobywania to wszystkie przykłady tej techniki.

W programowaniu komputerowym większość języków typu call-return opartych na stosie ma już wbudowane możliwości rekurencji: np.

• rozbij problem na mniejsze kawałki = = > wywołaj się na mniejszym podzbiorze oryginalnych danych),
• śledź, jak kawałki są dzielone = = > stosu połączeń,
• Stich the results back = = > stack-based return

Mam system, który używa czystej rekurencji ogonowej w kilku miejscach do symulacji maszyny stanowej.

Kilka świetnych przykładów rekursji można znaleźć w językach programowania funkcyjnego. W funkcyjnych językach programowania (Erlang, Haskell, ML/OCaml/F # , itd.), bardzo często zdarza się, że dowolne przetwarzanie list wykorzystuje rekurencję.

Gdy mamy do czynienia z listami w typowych językach imperatywnych OOP, bardzo często widzimy listy zaimplementowane jako listy połączone ([item1 -> item2 -> item3 -> item4]). Jednak w niektórych funkcjach programowania języki, można znaleźć, że listy same są zaimplementowane rekurencyjnie, gdzie "głowa" listy wskazuje na pierwszy element na liście, a "ogon" wskazuje na listę zawierającą resztę elementów ([item1 - > [item2 - > [item3 - > [item4 -> []]]]]). Moim zdaniem jest dość kreatywny.

Ta obsługa list, w połączeniu z dopasowywaniem wzorców, jest bardzo wydajna. Załóżmy, że chcę zsumować listę liczb:

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

To zasadniczo mówi: "gdybyśmy zostali wezwani z pustym list, return 0" (pozwalający na złamanie rekurencji), else return wartość head + wartość sumy wywołanej z pozostałymi elementami (stąd nasza rekurencja).

Na przykład, mogę mieć listę adresów URL , myślę, że rozbić wszystkie adresy URL, do których prowadzą linki URL, a następnie zmniejszyć całkowitą liczbę linków do / ze wszystkich adresów URL, aby wygenerować "wartości" dla strony (podejście, które Google przyjmuje z PageRank i które można znaleźć zdefiniowane w oryginalnym MapReduce papier). Możesz to zrobić, aby wygenerować liczbę słów również w dokumencie. I wiele, wiele, wiele innych rzeczy.

Możesz rozszerzyć ten wzorzec funkcjonalny na dowolny typ kodu MapReduce, w którym możesz wziąć listę czegoś, przekształcić ją i zwrócić coś innego (czy to inną listę, czy jakieś polecenie zip na liście).

XML, czyli przemierzanie wszystkiego co jest drzewem. Chociaż, szczerze mówiąc, w zasadzie nigdy nie używam rekurencji w mojej pracy.

Pętle sprzężenia zwrotnego w hierarchicznej organizacji.

Top boss mówi kierownikom najwyższego szczebla, aby zbierali opinie od wszystkich w firmie.

Każdy dyrektor zbiera swoje bezpośrednie raporty i mówi im, aby zbierali informacje zwrotne od swoich bezpośrednich raportów.

I dalej.

Ludzie bez bezpośrednich raportów -- węzły liści na drzewie -- dają swoje opinie.

Opinie wracają do drzewa, a każdy menedżer dodaje swój informacje zwrotne.

W końcu wszystkie opinie wracają do głównego bossa.

Jest To rozwiązanie naturalne, ponieważ metoda rekurencyjna umożliwia filtrowanie na każdym poziomie-zestawianie duplikatów i usuwanie obraźliwych sprzężeń zwrotnych. Top boss Może wysłać globalną wiadomość e-mail i przekazać każdemu pracownikowi informacje zwrotne bezpośrednio do niego, ale są problemy "nie możesz poradzić sobie z prawdą" i "jesteś zwolniony", więc rekurencja działa najlepiej tutaj.

Załóżmy, że budujesz CMS dla witryny, gdzie Twoje strony są w strukturze drzewa, z powiedzmy korzeniem strony głównej.

Załóżmy również, że twój {użytkownik / klient|klient / szef} prosi o umieszczenie ścieżki na każdej stronie, aby pokazać, gdzie jesteś w drzewie.

Dla danej strony n, możesz chcieć przejść do rodzica n i jego rodzica itd. rekurencyjnie, aby zbudować listę węzłów z powrotem do korzenia drzewa stron.

Oczywiście, że uderzasz db kilka razy na stronę w tym przykładzie, więc możesz użyć aliasingu SQL, w którym wyszukasz tabelę stron jako a, A tabelę stron ponownie jako b i połączysz a.id z B. parent więc bazy danych zrobić rekurencyjne połączenia. Minęło trochę czasu, więc moja składnia prawdopodobnie nie jest pomocna.

Z drugiej strony możesz tylko raz obliczyć tę wartość i zapisać ją wraz z rekordem strony, aktualizując ją tylko po przeniesieniu strony. To pewnie byłoby bardziej efektywne.

Anyway, that ' s my $.02

Masz drzewo organizacji, które jest N poziomy Głębokie. Kilka węzłów jest sprawdzonych i chcesz rozszerzyć je tylko na te węzły, które zostały sprawdzone.

To jest coś, co właściwie zakodowałem. To miłe i łatwe z rekurencją.

W mojej pracy Mamy system z ogólną strukturą danych, którą można opisać jako drzewo. Oznacza to, że rekurencja jest bardzo skuteczną techniką pracy z danymi.

Rozwiązanie go bez rekursji wymagałoby dużo niepotrzebnego kodu. Problem z rekurencją polega na tym, że nie jest łatwo śledzić to, co się dzieje. Naprawdę musisz się skoncentrować, śledząc przepływ egzekucji. Ale kiedy to działa, kod jest elegancki i skuteczny.

Obliczenia dla finansów / fizyki, takie jak średnie złożone.

• parsowanie pliku XML .
• efektywne wyszukiwanie w przestrzeniach wielowymiarowych. Np. quad-drzewa w 2D, oct-drzewa w 3D, KD-drzewa, itp.
• hierarchiczne grupowanie.
Jeśli o tym pomyśleć, przemierzanie dowolnej struktury hierarchicznej w naturalny sposób nadaje się do rekurencji.
• Metaprogramowanie szablonów w C++, gdzie nie ma pętli, a rekurencja jest jedynym sposobem.

Parsowanie drzewa kontrolek w Windows Forms lub WebForms (. NET Windows Forms / ASP.NET).

Najlepszym przykładem jaki znam jest quicksort , jest to o wiele prostsze z rekurencją. Spójrz na:

Shop.oreilly.com/product/9780596510046.do

Www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(kliknij na pierwszy podtytuł pod rozdziałem 3: "najpiękniejszy kod, jaki kiedykolwiek napisałem").

Firmy telefoniczne i kablowe utrzymują model ich topologii okablowania, który w efekcie jest dużą siecią lub wykresem. Rekurencja jest jednym ze sposobów przejścia tego modelu, gdy chcesz znaleźć wszystkie elementy nadrzędne lub potomne.

Ponieważ rekurencja jest kosztowna z punktu widzenia przetwarzania i pamięci, ten krok jest zwykle wykonywany tylko wtedy, gdy topologia zostanie zmieniona, a wynik jest przechowywany w zmodyfikowanym, wstępnie uporządkowanym formacie listy.

Rozumowanie indukcyjne, proces tworzenia koncepcji, ma charakter rekurencyjny. Twój mózg robi to cały czas, w prawdziwym świecie.

Tak samo komentarz o kompilatorach. Węzły drzewa abstrakcyjnej składni w naturalny sposób nadają się do rekurencji. Wszystkie rekurencyjne struktury danych (połączone listy, drzewa, wykresy itp.) są również łatwiejsze w obsłudze dzięki rekurencji. Myślę, że większość z nas nie korzysta często z rekurencji po skończeniu szkoły ze względu na rodzaje rzeczywistych problemów, ale dobrze jest być świadomym tego jako opcji.

Mnożenie liczb naturalnych jest rzeczywistym przykładem rekurencji:

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x