Esempi reali di ricorsione [chiuso]

Question

Quali sono i problemi del mondo reale in cui un approccio ricorsivo è la soluzione naturale oltre alla ricerca approfondita (DFS)?

(Non considero Torre di Hanoi , numero di Fibonacci , o problemi fattoriali del mondo reale. Sono un po 'inventati nella mia mente.)

Answer 1

Ci sono molti esempi di math qui, ma tu volevi un mondo reale , quindi con un po 'di pensiero, questo è forse il migliore che posso offrire:

Trovi una persona che ha contratto una determinata infezione contagiosa, che non è mortale, e si risolve rapidamente (Tipo A), ad eccezione di una persona su 5 (chiameremo questo tipo B) che si infetta permanentemente con essa e non mostra sintomi e agisce semplicemente come uno spargitore.

Questo crea ondate piuttosto fastidiose di caos quando mai il tipo B infetta una moltitudine di tipo A.

Il tuo compito è rintracciare tutti i tipi Bs e immunizzarli per fermare la spina dorsale della malattia. Sfortunatamente, tuttavia, non puoi amministrare una cura nazionale per tutti, perché le persone di tipo A sono anche mortalmente allergiche alla cura che funziona per il tipo B.

Il modo in cui lo faresti sarebbe la scoperta sociale, data una persona infetta (Tipo A), scegliere tutti i loro contatti nell'ultima settimana, segnando ogni contatto su un mucchio. Quando esegui il test di una persona infetta, aggiungila al " follow-up " coda. Quando una persona è di tipo B, aggiungila al " follow-up " alla testa (perché vuoi fermarti così in fretta).

Dopo aver elaborato una determinata persona, selezionare la persona dalla parte anteriore della coda e applicare l'immunizzazione, se necessario. Ottieni tutti i loro contatti precedentemente non visitati, quindi verifica se sono infetti.

Ripeti fino a quando la coda delle persone infette diventa 0, quindi attendi un altro scoppio ..

(Ok, questo è un po 'iterativo, ma è un modo iterativo di risolvere un problema ricorsivo, in questo caso, l'ampio attraversamento di una base di popolazione che cerca di scoprire probabili percorsi a problemi e, inoltre, le soluzioni iterative sono spesso più veloci e più efficace, e rimuovo compulsivamente la ricorsione dappertutto, tanto che diventa istintivo .... dannazione!)

Answer 2

Un esempio reale di ricorsione

Answer 3

Che ne dici di tutto ciò che coinvolge una struttura di directory nel file system. Ricerca ricorsiva di file, eliminazione di file, creazione di directory, ecc.

Ecco un'implementazione Java che stampa ricorsivamente il contenuto di una directory e delle sue sottodirectory.

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

}

Answer 4

Quicksort , merge sort e la maggior parte degli altri ordinamenti N-log.

Answer 5

L'esempio di Matt Dillard è buono. Più in generale, qualsiasi camminata di un albero può essere generalmente gestita con la ricorsione molto facilmente. Ad esempio, compilando alberi di analisi, camminando su XML o HTML, ecc.

Answer 6

La ricorsione è spesso utilizzata nelle implementazioni dell ' Backtracking algoritmo . Per un "mondo reale" applicazione di questo, che ne dici di un Risolutore di sudoku ?

Answer 7

La ricorsione è appropriata ogni volta che un problema può essere risolto dividendolo in sotto-problemi, che possono utilizzare lo stesso algoritmo per risolverli. Gli algoritmi sugli alberi e gli elenchi ordinati sono una scelta naturale. Molti problemi nella geometria computazionale (e nei giochi 3D) possono essere risolti in modo ricorsivo usando partizionamento dello spazio binario (BSP ) alberi, suddivisioni grasse , o altri modi per dividere il mondo in sotto-parti.

La ricorsione è appropriata anche quando si cerca di garantire la correttezza di un algoritmo. Data una funzione che accetta input immutabili e restituisce un risultato che è una combinazione di chiamate ricorsive e non ricorsive sugli input, di solito è facile dimostrare che la funzione è corretta (o no) usando l'induzione matematica. È spesso intrattabile farlo con una funzione iterativa o con input che possono mutare. Ciò può essere utile quando si ha a che fare con calcoli finanziari e altre applicazioni in cui la correttezza è molto importante.

Answer 8

Sicuramente molti compilatori là fuori usano pesantemente la ricorsione. I linguaggi informatici sono intrinsecamente ricorsivi (ad esempio, è possibile incorporare istruzioni "if" all'interno di altre istruzioni "if", ecc.)

Answer 9

Disabilitazione / impostazione di sola lettura per tutti i controlli figlio in un controllo contenitore. Ho dovuto farlo perché alcuni dei controlli dei bambini erano contenitori stessi.

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

Answer 10

Ciclo famoso di valutazione / applicazione da SICP

_{(fonte: mit.edu )}

Ecco la definizione di 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))))

Ecco la definizione di apply:

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

Ecco la definizione di eval-sequence:

(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 - > applica - > eval-sequence - > eval

Answer 11

La ricorsione è usata in cose come gli alberi BSP per il rilevamento delle collisioni nello sviluppo del gioco (e altre aree simili).

Answer 12

Le persone spesso ordinano pile di documenti usando un metodo ricorsivo. Ad esempio, immagina di ordinare 100 documenti con nomi su di essi. Posiziona prima i documenti in pile per la prima lettera, quindi ordina ogni pila.

La ricerca di parole nel dizionario è spesso eseguita da una tecnica simile alla ricerca binaria, che è ricorsiva.

Nelle organizzazioni, i capi spesso impartiscono comandi ai capi dipartimento, che a loro volta impartiscono comandi ai dirigenti e così via.

Answer 13

I parser e i compilatori possono essere scritti in un metodo di discesa ricorsiva. Non è il modo migliore per farlo, poiché strumenti come lex / yacc generano parser più veloci ed efficienti, ma concettualmente semplici e facili da implementare, quindi rimangono comuni.

Answer 14

Requisiti del mondo reale che ho ricevuto di recente:

Requisito A: implementare questa funzione dopo aver compreso a fondo il requisito A.

Answer 15

La ricorsione è applicata a problemi (situazioni) in cui è possibile suddividerla (ridurla) in parti più piccole e ciascuna parte è simile al problema originale.

Buoni esempi di dove sono le cose che contengono parti più piccole simili a se stesse:

• struttura ad albero (un ramo è come un albero)
• elenchi (parte di un elenco è ancora un elenco)
• contenitori (bambole russe)
• sequenze (parte di una sequenza è simile alla successiva)
• gruppi di oggetti (un sottogruppo è ancora un gruppo di oggetti)

La ricorsione è una tecnica per continuare a scomporre il problema in pezzi sempre più piccoli, fino a quando uno di quei pezzi diventa abbastanza piccolo da essere un pezzo di torta. Ovviamente, dopo averli scomposti, dovrai quindi "cucire". i risultati tornano insieme nel giusto ordine per formare una soluzione totale al tuo problema originale.

Alcuni algoritmi di ordinamento ricorsivo, algoritmi di camminata sugli alberi, algoritmi di mappatura / riduzione, divisione e conquista sono tutti esempi di questa tecnica.

Nella programmazione per computer, la maggior parte dei linguaggi di tipo call-return basati su stack ha già le funzionalità integrate per la ricorsione: ad es.

• scomponi il problema in pezzi più piccoli == > chiamarsi su un sottoinsieme più piccolo dei dati originali),
• tieni traccia di come sono divisi i pezzi == > call stack,
• ricama i risultati indietro == > ritorno basato sullo stack

Answer 16

Ho un sistema che utilizza ricorsione della coda in alcuni punti per simulare uno stato macchina.

Answer 17

Alcuni grandi esempi di ricorsione si trovano nelle lingue programmazione funzionale . Nei linguaggi di programmazione funzionale ( Erlang , Haskell , ML / OCaml / F # , ecc.), è molto comune che qualsiasi elaborazione dell'elenco utilizzi la ricorsione.

Quando si ha a che fare con elenchi in linguaggi imperativi tipici in stile OOP, è molto comune vedere gli elenchi implementati come elenchi collegati ([item1 - > item2 - > item3 - > item4]). Tuttavia, in alcuni linguaggi di programmazione funzionale, si scopre che gli elenchi stessi sono implementati in modo ricorsivo, dove la "testa" dell'elenco punta al primo elemento dell'elenco e la "coda" indica un elenco contenente il resto degli elementi ([item1 - > [item2 - > [item3 - > [item4 - > []]]]). Secondo me è piuttosto creativo.

Questa gestione degli elenchi, se combinata con la corrispondenza dei modelli, è MOLTO potente. Diciamo che voglio sommare un elenco di numeri:

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

Questo essenzialmente dice "se fossimo chiamati con un elenco vuoto, restituire 0" (permettendoci di interrompere la ricorsione), altrimenti restituisce il valore di head + il valore di Sum chiamato con gli elementi rimanenti (quindi, la nostra ricorsione).

Ad esempio, potrei avere un elenco di URL , penso che divida tutto URL a cui ciascun URL rimanda, quindi riduco il numero totale di collegamenti a / da tutti gli URL per generare "valori" per una pagina (un approccio adottato da Google con PageRank e che puoi trovare definito nell'originale MapReduce ). Puoi farlo anche per generare conteggi di parole in un documento. E molte, molte, anche molte altre cose.

Puoi estendere questo modello funzionale a qualsiasi tipo di MapReduce dove puoi prendere un codice elenco di qualcosa, trasformandolo e restituendo qualcos'altro (se un altro elenco o un comando zip nell'elenco).

Answer 18

XML, o attraversando tutto ciò che è un albero. Anche se, a dire il vero, non uso quasi mai la ricorsione nel mio lavoro.

Answer 19

Cicli di feedback in un'organizzazione gerarchica.

Il capo principale dice ai dirigenti di raccogliere feedback da tutti i membri dell'azienda.

Ogni dirigente raccoglie i suoi rapporti diretti e dice loro di raccogliere feedback dai loro rapporti diretti.

E lungo la linea.

Le persone senza report diretti - i nodi foglia nella struttura ad albero - danno il loro feedback.

Il feedback si sposta sull'albero con ogni manager che aggiunge il proprio feedback.

Alla fine tutto il feedback arriva al capo principale.

Questa è la soluzione naturale perché il metodo ricorsivo consente di filtrare ad ogni livello: la raccolta di duplicati e la rimozione di feedback offensivi. Il capo superiore potrebbe inviare un'e-mail globale e fare in modo che ciascun dipendente riporti direttamente il feedback a lui / lei, ma ci sono le "quot" che non puoi gestire la verità " e il " sei licenziato " problemi, quindi la ricorsione funziona meglio qui.

Answer 20

Supponiamo che tu stia costruendo un CMS per un sito Web, dove le tue pagine sono in una struttura ad albero, con la radice che è la home page.

Supponi anche che il tuo {utente | client | cliente | capo} ti richieda di inserire una traccia breadcrumb su ogni pagina per mostrare dove ti trovi nella struttura.

Per ogni data pagina n, potresti voler camminare verso il genitore di n, e il suo genitore, e così via, ricorsivamente per costruire un elenco di nodi fino alla radice dell'albero della pagina.

Ovviamente, stai colpendo il db più volte per pagina in quell'esempio, quindi potresti voler usare un po 'di alias SQL dove cerchi la tabella delle pagine come a, e la tabella delle pagine di nuovo come b, e unisci un .id con b.parent in modo che il database esegua i join ricorsivi. È passato un po 'di tempo, quindi la mia sintassi probabilmente non è stata utile.

Quindi, potresti voler solo calcolare questo una volta e memorizzarlo con il record di pagina, aggiornandolo solo se sposti la pagina. Sarebbe probabilmente più efficiente.

Comunque, quello è il mio $ .02

Answer 21

Hai un albero organizzativo con N livelli di profondità. Molti dei nodi sono stati controllati e si desidera espandere solo i nodi che sono stati controllati.

Questo è qualcosa che ho effettivamente codificato. È bello e facile con la ricorsione.

Answer 22

Nel mio lavoro abbiamo un sistema con una struttura di dati generica che può essere descritta come una struttura ad albero. Ciò significa che la ricorsione è una tecnica molto efficace per lavorare con i dati.

Risolverlo senza ricorsione richiederebbe molto codice non necessario. Il problema con la ricorsione è che non è facile seguire ciò che accade. Devi davvero concentrarti quando segui il flusso di esecuzione. Ma quando funziona il codice è elegante ed efficace.

Answer 23

Calcoli per finanza / fisica, come medie composte.

Answer 24

• Analisi di un XML .
• Ricerca efficiente in spazi multidimensionali. Per esempio. quad-alberi in 2D, oct-alberi in 3D, kd-alberi, ecc.
• Cluster gerarchico.
• Vieni a pensarci bene, attraversare qualsiasi struttura gerarchica si presta naturalmente alla ricorsione.
• Metaprogrammazione dei template in C ++, dove non ci sono loop e la ricorsione è l'unico modo.

Answer 25

Analisi di un albero di controlli in Windows Form o WebForms (.NET Windows Form / < a href = "http://en.wikipedia.org/wiki/ASP.NET" rel = "nofollow noreferrer"> ASP.NET ).

Answer 26

Il miglior esempio che conosco è quicksort , è molto più semplice con la ricorsione. Dai un'occhiata a:

shop.oreilly.com/product/9780596510046.do

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

(Fai clic sul primo sottotitolo nel capitolo 3: " Il codice più bello che abbia mai scritto ").

Answer 27

Le compagnie telefoniche e via cavo mantengono un modello della loro topologia di cablaggio, che in effetti è una grande rete o un grafico. La ricorsione è un modo per attraversare questo modello quando vuoi trovare tutti gli elementi genitore o figlio.

Poiché la ricorsione è costosa dal punto di vista dell'elaborazione e della memoria, questo passaggio viene generalmente eseguito solo quando la topologia viene modificata e il risultato viene archiviato in un formato elenco preordinato modificato.

Answer 28

Il ragionamento induttivo, il processo di formazione dei concetti, è di natura ricorsiva. Il tuo cervello lo fa sempre, nel mondo reale.

Answer 29

Idem il commento sui compilatori. I nodi dell'albero di sintassi astratti si prestano naturalmente alla ricorsione. Tutte le strutture di dati ricorsive (elenchi collegati, alberi, grafici, ecc.) Sono inoltre gestite più facilmente con la ricorsione. Penso che la maggior parte di noi non riesca ad usare molto la ricorsione una volta che siamo fuori dalla scuola a causa dei tipi di problemi del mondo reale, ma è bene esserne consapevoli come opzione.

Answer 30

La moltiplicazione dei numeri naturali è un esempio reale di ricorsione:

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