Jakie są rzeczywiste problemy, w których podejście rekurencyjne jest naturalnym rozwiązaniem poza przeszukiwaniem najpierw w głąb (DFS)?
(Nie biorę pod uwagę Wieży Hanoi , liczby Fibonacciego ani czynników silni w świecie rzeczywistym. Są trochę wymyślone w mojej głowie).
Odpowiedzi:
Jest tu wiele przykładów matematycznych, ale chciałeś mieć przykład z prawdziwego świata , więc przy odrobinie przemyślenia jest to prawdopodobnie najlepsze, co mogę zaoferować:
Znajdziesz osobę, która zaraziła się daną infekcją zakaźną, która nie jest śmiertelna i szybko ustępuje (typ A), z wyjątkiem jednej na 5 osób (nazwiemy to typ B), która zostaje trwale zakażona i nie wykazuje objawy i działa jedynie jako rozprzestrzenianie.
Powoduje to dość denerwujące fale spustoszenia, gdy kiedykolwiek typ B infekuje wiele typów A.
Twoim zadaniem jest wytropienie wszystkich typów B i uodpornienie ich, aby zatrzymać kręgosłup choroby. Niestety, nie możesz wszystkim podać ogólnokrajowego lekarstwa, ponieważ ludzie z typem A są również śmiertelnie uczuleni na lek, który działa na typ B.
Sposób, w jaki można to zrobić, polegałby na odkryciu społecznym, biorąc pod uwagę zarażoną osobę (typ A), wybranie wszystkich jej kontaktów w ostatnim tygodniu, zaznaczając każdy kontakt na stosie. Kiedy sprawdzasz, czy osoba jest zarażona, dodaj ją do kolejki „follow up”. Kiedy osoba jest typu B, dodaj ją do „kontynuacji” na początku (ponieważ chcesz to szybko zatrzymać).
Po przetworzeniu danej osoby należy wybrać osobę z przodu kolejki i w razie potrzeby zaszczepić. Zbierz wszystkie ich kontakty, które wcześniej nie były odwiedzane, a następnie przetestuj, czy są zainfekowane.
Powtarzaj, aż kolejka zarażonych osób osiągnie wartość 0, a następnie poczekaj na kolejną epidemię.
(Ok, jest to trochę iteracyjne, ale jest to iteracyjny sposób rozwiązywania problemu rekurencyjnego, w tym przypadku szerokość pierwszego przejścia bazy populacji próbującej odkryć prawdopodobne ścieżki problemów, a poza tym rozwiązania iteracyjne są często szybsze i skuteczniejsze i kompulsywnie usuwam rekursję wszędzie, tak bardzo, że stała się ona instynktowna. .... cholera!)
Co powiesz na wszystko, co dotyczy struktury katalogów w systemie plików. Rekurencyjne wyszukiwanie plików, usuwanie plików, tworzenie katalogów itp.
Oto implementacja Java, 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 , sortowanie przez scalanie , a większość innych sortuje N N-log.
Przykład Matta Dillarda jest dobry. Mówiąc bardziej ogólnie, każde chodzenie po drzewie może być bardzo łatwo obsługiwane przez rekursję. Na przykład kompilowanie drzew parsowania, przechodzenie po XML lub HTML itp.
Rekursja jest często używana w implementacjach algorytmu Backtracking . Jeśli chodzi o zastosowanie tego w „prawdziwym świecie”, co powiesz na rozwiązanie Sudoku ?
Rekursja jest odpowiednia, gdy problem można rozwiązać, dzieląc go na podproblemy, które mogą używać tego samego algorytmu do ich rozwiązywania. Algorytmy na drzewach i posortowanych listach są do siebie dopasowane. Wiele problemów związanych z geometrią obliczeniową (i grami 3D) można rozwiązać rekurencyjnie, stosując drzewa binarnego podziału przestrzeni (BSP), podziały grube lub inne sposoby dzielenia świata na części.
Rekurencja jest również odpowiednia, gdy próbujesz zagwarantować poprawność algorytmu. Biorąc pod uwagę funkcję, która przyjmuje niezmienne dane wejściowe i zwraca wynik będący połączeniem rekurencyjnych i nierekurencyjnych wywołań danych wejściowych, zwykle łatwo jest udowodnić, że funkcja jest poprawna (lub nie) za pomocą indukcji matematycznej. Często jest to trudne do zrobienia za pomocą funkcji iteracyjnej lub danych wejściowych, które mogą ulegać mutacjom. Może to być przydatne w przypadku obliczeń finansowych i innych zastosowań, w których bardzo ważna jest poprawność.
Z pewnością wiele kompilatorów intensywnie korzysta z rekurencji. Języki komputerowe są z natury rekurencyjne (tzn. Można osadzić instrukcje „if” w innych instrukcjach „if” itp.).
Wyłączanie / ustawianie tylko do odczytu dla wszystkich formantów podrzędnych w kontrolce kontenera. Musiałem to zrobić, ponieważ niektóre kontrolki dzieci same 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);
}
}
(źródło: mit.edu )
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 zastosowania:
(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
Ludzie często sortują stosy dokumentów metodą rekurencyjną. Na przykład wyobraź sobie, że sortujesz 100 dokumentów z nazwami. Najpierw ułóż dokumenty w stosach według pierwszej litery, a następnie posortuj każdy stos.
Wyszukiwanie słów w słowniku często odbywa się za pomocą techniki przypominającej wyszukiwanie binarne, która jest rekurencyjna.
W organizacjach szefowie często wydają polecenia szefom działów, którzy z kolei wydają polecenia menedżerom i tak dalej.
Rekurencja jest stosowana do problemów (sytuacji), w których można ją podzielić (zredukować) na mniejsze części, a każda część wygląda podobnie do pierwotnego problemu.
Dobre przykłady sytuacji, w których rzeczy zawierające mniejsze części podobne do siebie to:
Rekurencja to technika polegająca na rozkładaniu problemu na coraz mniejsze części, dopóki jeden z nich nie stanie się wystarczająco mały, by stać się bułką z masłem. Oczywiście, po ich rozbiciu, musisz następnie „zszyć” wyniki w odpowiedniej kolejności, aby stworzyć całkowite rozwiązanie pierwotnego problemu.
Niektóre algorytmy rekurencyjne sortowania, algorytmy poruszania się po drzewie, algorytmy mapowania / redukcji, dziel i rządź są przykładami tej techniki.
W programowaniu komputerowym większość języków typu call-return opartych na stosie ma już wbudowane możliwości rekurencji: tj
Mam system, który używa czystej rekurencji ogona w kilku miejscach do symulacji maszyny stanu.
Kilka wspaniałych przykładów rekursji można znaleźć w funkcjonalnych językach programowania . W funkcjonalnych językach programowania ( Erlang , Haskell , ML / OCaml / F # itp.) Bardzo często wykorzystuje się rekursję do przetwarzania list.
Gdy mamy do czynienia z listami w typowych, imperatywnych językach w stylu OOP, bardzo często spotyka się listy zaimplementowane jako listy połączone ([item1 -> item2 -> item3 -> item4]). Jednak w niektórych funkcjonalnych językach programowania można zauważyć, że same listy są implementowane rekurencyjnie, gdzie „nagłówek” listy wskazuje na pierwszą pozycję na liście, a „koniec” wskazuje na listę zawierającą pozostałe elementy ( [item1 -> [item2 -> [item3 -> [item4 -> []]]]]). Moim zdaniem jest dość kreatywny.
Ta obsługa list, w połączeniu z dopasowywaniem wzorców, jest BARDZO potężna. Powiedzmy, że chcę podsumować listę liczb:
let rec Sum numbers =
match numbers with
| [] -> 0
| head::tail -> head + Sum tail
Zasadniczo mówi to „jeśli wywołano nas z pustą listą, zwróć 0” (co pozwoli nam przerwać rekursję), w przeciwnym razie zwróć wartość head + wartość sumy wywołanej z pozostałymi elementami (stąd nasza rekursja).
Na przykład, mogę mieć listę adresów URL , myślę, że rozbijam wszystkie adresy URL, do których prowadzi każdy adres URL, a następnie zmniejszam całkowitą liczbę linków do / ze wszystkich adresów URL, aby wygenerować „wartości” dla strony (podejście, które Google ma PageRank i które można znaleźć w oryginalnym artykule MapReduce ). 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 pobrać listę czegoś, przekształcić ją i zwrócić coś innego (czy to inna lista, czy jakieś polecenie zip na liście).
XML lub przechodzenie przez wszystko, co jest drzewem. Chociaż, szczerze mówiąc, prawie nigdy nie używam rekurencji w mojej pracy.
Pętle informacji zwrotnych w organizacji hierarchicznej.
Najwyższy szef mówi najwyższemu kierownictwu, aby zebrał informacje zwrotne od wszystkich w firmie.
Każdy menedżer zbiera swoich bezpośrednich podwładnych i każe im zbierać informacje zwrotne od swoich bezpośrednich podwładnych.
I dalej.
Osoby bez bezpośrednich podwładnych - węzły liści w drzewie - przekazują swoje opinie.
Informacje zwrotne wędrują po drzewie, a każdy menedżer dodaje własne opinie.
Ostatecznie cała informacja zwrotna trafia do szefa.
Jest to naturalne rozwiązanie, ponieważ metoda rekurencyjna umożliwia filtrowanie na każdym poziomie - zestawianie duplikatów i usuwanie obraźliwych sprzężeń. Szef może wysłać globalną wiadomość e-mail i poprosić każdego pracownika o przesłanie opinii bezpośrednio do niego / niej, ale są problemy typu „nie radzisz sobie z prawdą” i „jesteś zwolniony”, więc rekurencja działa tutaj najlepiej.
Załóżmy, że tworzysz system CMS dla witryny internetowej, w której Twoje strony są w strukturze drzewa, na przykład w katalogu głównym jest strona główna.
Załóżmy również, że Twój {user | client | customer | boss} żąda umieszczenia ścieżki nawigacyjnej na każdej stronie, aby pokazać, gdzie jesteś w drzewie.
Dla dowolnej strony n możesz chcieć podejść do elementu nadrzędnego n, jego elementu nadrzędnego itd., Rekurencyjnie, aby utworzyć listę węzłów z powrotem do korzenia drzewa stron.
Oczywiście w tym przykładzie wciskasz bazę danych kilka razy na stronę, więc możesz chcieć użyć aliasingu SQL, w którym wyszukujesz tablicę stron jako a, a tablicę stron ponownie jako b i łączysz a.id z b.parent, więc sprawisz, że baza danych będzie wykonywać sprzężenia rekurencyjne. Minęło trochę czasu, więc moja składnia prawdopodobnie nie jest pomocna.
Z drugiej strony możesz po prostu obliczyć to tylko raz i zapisać go z rekordem strony, aktualizując go tylko wtedy, gdy przesuniesz stronę. To prawdopodobnie byłoby bardziej wydajne.
W każdym razie to moje 0,02 dolara
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żej ilości niepotrzebnego kodu. Problem z rekurencją polega na tym, że nie jest łatwo śledzić, co się dzieje. Naprawdę musisz się skoncentrować, śledząc przebieg wykonania. Ale kiedy to działa, kod jest elegancki i skuteczny.
Analizowanie drzewa formantów w Windows Forms lub WebForms (.NET Windows Forms / ASP.NET ).
Najlepszym przykładem, jaki znam, jest szybkie sortowanie , rekurencja jest o wiele prostsza. Spojrzeć na:
shop.oreilly.com/product/9780596510046.do
www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047
(Kliknij pierwszy podtytuł pod rozdziałem 3: „Najpiękniejszy kod, jaki kiedykolwiek napisałem”).
Firmy telekomunikacyjne i kablowe utrzymują model topologii okablowania, który w efekcie jest dużą siecią lub wykresem. Rekursja jest jednym ze sposobów przechodzenia przez ten model, gdy chcesz znaleźć wszystkie elementy nadrzędne lub podrzędne.
Ponieważ rekursja jest kosztowna z punktu widzenia przetwarzania i pamięci, ten krok jest zwykle wykonywany tylko wtedy, gdy topologia jest zmieniana, a wynik jest przechowywany w zmodyfikowanym formacie listy uporządkowanej.
Podobnie jak komentarz o kompilatorach. Węzły drzewa składni abstrakcyjnej naturalnie nadają się do rekurencji. Wszystkie rekurencyjne struktury danych (połączone listy, drzewa, wykresy itp.) Są również łatwiejsze w obsłudze dzięki rekursji. Myślę, że większość z nas nie używa często rekurencji, gdy wychodzimy poza szkołę z powodu różnych problemów w świecie rzeczywistym, ale dobrze jest mieć tego świadomość jako opcję.