Esempi di funzioni ricorsive

Qualcuno può suggerire esempi di programmazione che illustrano le funzioni ricorsive? Ci sono i soliti vecchi cavalli come la serie di Fibonacci e le Torri di Hanoi , ma qualsiasi cosa oltre a loro sarebbe divertente.

Questa illustrazione è in inglese, piuttosto che un vero e proprio linguaggio di programmazione, ma è utile per spiegare il processo in modo non tecnico:

 Un bambino non poteva dormire, così sua madre raccontò una storia su una piccola rana,
   chi non riusciva a dormire, così la madre della rana raccontò una storia su un piccolo orso,
      Chi non riusciva a dormire, così la madre di Bear raccontò una storia su una piccola donnola
        ... che si è addormentato.
      ... e l'orsetto si addormentò;
   ... e la piccola rana si addormentò;
 ... e il bambino si addormentò.

Per capire la ricorsione , bisogna prima capire la ricorsione .

La regola generale per la ricorsione è, “Usa ricorsione, se e solo se su ogni iterazione il tuo compito si divide in due o più attività simili”.

Quindi Fibonacci non è un buon esempio di applicazione di ricorsione, mentre Hanoi è un buon esempio.

Quindi la maggior parte dei buoni esempi di ricorsione sono l’attraversamento di alberi in diversi disagi.

Ad esempio: attraversamento del grafico – il requisito che il nodo visitato non sarà mai più visitato di nuovo rende effettivamente graficamente un albero (un albero è un grafico connesso senza cicli semplici)

dividere e conquistare gli algoritmi (ordinamento rapido, unisci ordinamento) – le parti dopo “dividi” costituiscono nodes figli, “conquisti” costituiscono i bordi dal nodo genitore ai nodes figli.

Che ne dici di testare una stringa per essere un palindromo?

bool isPalindrome(char* s, int len) { if(len < 2) return TRUE; else return s[0] == s[len-1] && isPalindrome(&s[1], len-2); } 

Certo, potresti farlo con un loop in modo più efficiente.

Scrivi un parser di discesa ricorsivo !

Un altro paio di “soliti sospetti” sono Quicksort e MergeSort

Dal mondo della matematica, c’è la funzione di Ackermann :

 Ackermann(m, n) { if(m==0) return n+1; else if(m>0 && n==0) return Ackermann(m-1, 1); else if(m>0 && n>0) return Ackermann(m-1, Ackermann(m, n-1)); else throw exception; //not defined for negative m or n } 

Termina sempre, ma produce risultati estremamente grandi anche per input molto piccoli. Ackermann (4, 2), ad esempio, restituisce 2 65536 – 3.

Il modello di progettazione dell’interprete è un esempio abbastanza carino perché molte persone non individuano la ricorsione. Il codice di esempio elencato nell’articolo di Wikipedia illustra bene come questo può essere applicato. Tuttavia, un approccio molto più basilare che implementa ancora il modello dell’interprete è una funzione ToString per gli elenchi annidati:

 class List { public List(params object[] items) { foreach (object o in items) this.Add(o); } // Most of the implementation omitted … public override string ToString() { var ret = new StringBuilder(); ret.Append("( "); foreach (object o in this) { ret.Append(o); ret.Append(" "); } ret.Append(")"); return ret.ToString(); } } var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7); Console.WriteLine(lst); // yields: // ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 ) 

(Sì, so che non è facile individuare il pattern dell’interprete nel codice sopra se ti aspetti una funzione chiamata Eval … ma in realtà, il pattern dell’interprete non ci dice come viene chiamata la funzione o anche cosa fa e il book GoF elenca esplicitamente quanto sopra come un esempio di detto modello.)

A mio parere, la ricorsione è buona cosa, ma la maggior parte delle soluzioni che potrebbero utilizzare la ricorsione potrebbe anche essere eseguita utilizzando l’iterazione e l’iterazione è di gran lunga più efficiente.

Ciò detto qui è un modo ricorsivo per trovare un controllo in un albero nidificato (come ASP.NET o Winforms):

 public Control FindControl(Control startControl, string id) { if (startControl.Id == id) return startControl if (startControl.Children.Count > 0) { foreach (Control c in startControl.Children) { return FindControl(c, id); } } return null; } 

Ecco un esempio pragmatico dal mondo dei filesystem. Questa utilità conta in modo ricorsivo i file in una directory specificata. (Non ricordo perché, ma in realtà ho avuto bisogno di qualcosa di simile molto tempo fa …)

 public static int countFiles(File f) { if (f.isFile()){ return 1; } // Count children & recurse into subdirs: int count = 0; File[] files = f.listFiles(); for (File fileOrDir : files) { count += countFiles(fileOrDir); } return count; } 

(Si noti che in Java un’istanza File può rappresentare un file normale o una directory.Questa utility esclude le directory dal conteggio.)

Un esempio comune nel mondo reale sarebbe ad es. FileUtils.deleteDirectory() dalla libreria IO dei Commons ; guarda l’ API doc e la fonte .

Un esempio reale è il problema del “costo delle materie prime”.

Supponiamo di avere un’azienda manifatturiera che produce prodotti finali. Ogni prodotto è descrivibile da un elenco delle sue parti e il tempo necessario per assemblare quelle parti. Ad esempio, produciamo trapani elettrici manuali da una cassa, un motore, un mandrino, un interruttore e un cavo, e impiega 5 minuti.

Dato un costo del lavoro standard al minuto, quanto costa produrre ciascuno dei nostri prodotti?

Oh, a proposito, alcune parti (ad es. Il cavo) sono state acquistate, quindi ne conosciamo direttamente il costo.

Ma produciamo effettivamente alcune parti noi stessi. Realizziamo un motore con un alloggiamento, uno statore, un rotore, un albero e cuscinetti, e impiega 15 minuti.

E facciamo lo statore e il rotore di timbri e fili, …

Quindi, determinare il costo di un prodotto finito equivale effettivamente a attraversare l’albero che rappresenta tutte le relazioni da intero a elenco di parti nei nostri processi. Questo è ben express con un algoritmo ricorsivo. Può anche essere fatto in modo iterativo, ma l’idea centrale si mescola con la contabilità da fare da soli, quindi non è chiaro cosa sta succedendo.

L’esempio più sexy che conosco è Knuth’s Man o Boy Test . Oltre alla ricorsione utilizza le funzioni di Algol delle definizioni di funzioni annidate (chiusure), i riferimenti di funzione e il dualismo costante / funzione (chiamata per nome).

Come altri hanno già detto, molti esempi di ricorsione canonica sono accademici.

Alcuni usi pratici che ho incontrato in passato sono:

1 – Navigazione in una struttura ad albero, come un file system o il registro

2 – Manipolazione dei controlli del contenitore che possono contenere altri controlli del contenitore (come Pannelli o GroupBox)

Il mio preferito è la ricerca binaria

Modifica: Inoltre, attraversa l’albero. Camminando per esempio su una struttura di file di cartelle.

Implementare grafici di Guido van Rossum ha alcune funzioni ricorsive in Python per trovare percorsi tra due nodes nei grafici.

Il mio tipo preferito, Unisci Ordina

(Preferito dal momento che posso ricordare l’algoritmo e non è troppo cattivo dal punto di vista delle prestazioni)

  • Fattoriale
  • Attraversare un albero in profondità (in un filesystem, in uno spazio di gioco o in qualsiasi altro caso)

Che ne dici di invertire una stringa?

 void rev(string s) { if (!s.empty()) { rev(s[1..s.length]); } print(s[0]); } 

Comprendere ciò aiuta a capire la ricorsione.

Ecco un esempio che ho postato su questo sito qualche tempo fa per generare ricorsivamente un albero di menu: Esempio ricorsivo

Che ne dici di qualsiasi elaborazione di elenchi , come:

  • map (e andmap, ormap)
  • piega (piega, piega)
  • filtro
  • eccetera…

C’era una volta, e non molto tempo fa, i bambini delle elementari imparavano la ricorsione usando Logo e Turtle Graphics. http://en.wikipedia.org/wiki/Turtle_graphics

La ricorsione è anche ottima per risolvere enigmi con un processo completo. C’è una sorta di puzzle chiamato “riempimento” (Google it) in cui si ottiene una griglia come un cruciverba e le parole, ma senza indizi, senza quadrati numerati. Una volta ho scritto un programma usando la ricorsione per un editore di puzzle per risolvere i puzzle per essere sicuro che la soluzione conosciuta fosse unica.

Le funzioni ricorsive sono ottime per lavorare con tipi di dati definiti in modo ricorsivo :

  • Un numero naturale è zero o il successore di un altro numero naturale
  • Una lista è la lista vuota o un’altra lista con un elemento in primo piano
  • Un albero è un nodo con alcuni dati e zero o più altri sottoalberi

Eccetera.

Traduci un indice di colonna di un foglio di lavoro con un nome di colonna.

È più difficile di quanto sembri, perché le colonne del foglio di calcolo non gestiscono correttamente la cifra “0”. Ad esempio, se prendi AZ come cifre quando passi da Z a AA, sarebbe come andare da 9 a 11 o da 9 a 00 anziché 10 (a seconda che A sia 1 o 0). Anche l’ esempio di supporto Microsoft si sbaglia per qualcosa di più alto di AAA!

La soluzione ricorsiva funziona perché puoi recitare direttamente su quei limiti di nuova cifra. Questa implementazione è in VB.Net e tratta la prima colonna (‘A’) come indice 1.

 Function ColumnName(ByVal index As Integer) As String Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c} index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column' Dim quotient As Integer = index \ 26 'normal / operator rounds. \ does integer division' If quotient > 0 Then Return ColumnName(quotient) & chars(index Mod 26) Else Return chars(index Mod 26) End If End Function