Quasi tutti gli articoli che posso trovare sulla ricorsione includono gli esempi di numeri fattoriali o di Fibonacci, che sono:
Esistono alcuni esempi di codice non matematici interessanti per insegnare la ricorsione?
Sto pensando ad algoritmi di divisione e conquista, ma di solito coinvolgono strutture dati complesse.
Le strutture di directory / file sono il miglior esempio di utilizzo per la ricorsione, perché tutte le comprendono prima di iniziare, ma qualsiasi cosa implichi strutture ad albero lo farà.
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;
}
Cerca le cose che coinvolgono strutture ad albero. Un albero è relativamente facile da afferrare e la bellezza di una soluzione ricorsiva diventa evidente molto prima che con strutture di dati lineari come le liste.
Cose a cui pensare:
Questi sono tutti correlati agli scenari reali reali e possono essere tutti utilizzati in applicazioni di significato reale.
Ecco alcuni altri problemi pratici che mi vengono in mente:
QuickSort sarebbe il primo a salirci in mente. Anche la ricerca binaria è un problema ricorsivo. Oltre a ciò ci sono intere classi di problemi che le soluzioni cadono quasi gratis quando si inizia a lavorare con la ricorsione.
Ordina, definito ricorsivamente in Python.
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 )
Unisci, definito in modo ricorsivo.
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:])
Ricerca lineare, definita in modo ricorsivo.
def find( element, sequence ):
if len(sequence) == 0: return False
if element == sequence[0]: return True
return find( element, sequence[1:] )
Ricerca binaria, definita in modo ricorsivo.
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:] )
In un certo senso, la ricorsione riguarda tutte le soluzioni di divisione e conquista, ovvero lo spazio del problema in uno più piccolo per aiutare a trovare la soluzione per un problema semplice, e quindi tornare indietro nel ricostruire il problema originale per comporre la risposta giusta .
Alcuni esempi che non implicano la matematica per insegnare la ricorsione (almeno quei problemi che ricordo nei miei anni universitari):
Questi sono esempi di utilizzo del Backtracking per risolvere il problema.
Altri problemi sono i classici del dominio di Intelligenza Artificiale: Usando Depth First Search, pathfinding, planning.
Tutti questi problemi implicano una sorta di struttura dati "complessa", ma se non vuoi insegnarlo con la matematica (numeri), le tue scelte potrebbero essere più limitate. Yoy potrebbe voler iniziare a insegnare con una struttura dati di base, come una lista collegata. Ad esempio, rappresenta i numeri naturali usando una lista:
0 = elenco vuoto 1 = elenco con un nodo. 2 = elenco con 2 nodi. ...
quindi definire la somma di due numeri in termini di questa struttura dati come questa: Vuoto + N = N Nodo (X) + N = Nodo (X + N)
Towers of Hanoi è una buona soluzione per aiutarti a imparare la ricorsione.
Ci sono molte soluzioni sul web in molte lingue diverse.
Un rilevatore Palindromo:
Inizia con una stringa: "ABCDEEDCBA" Se si avvia & i caratteri finali sono uguali, quindi ricorri e verifica "BCDEEDCB", ecc.
Nei linguaggi di programmazione funzionale, quando non sono disponibili funzioni di ordine superiore, viene utilizzata la ricorsione anziché i cicli imperiali per evitare lo stato mutabile.
F # è un linguaggio funzionale impuro che consente entrambi gli stili, quindi confronterò entrambi qui. La seguente somma di tutti i numeri in una lista.
Anello imperativo con variabile mutabile
let xlist = [1;2;3;4;5;6;7;8;9;10]
let mutable sum = 0
for x in xlist do
sum <- sum + x
Ciclo ricorsivo senza stato mutevole
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
Si noti che questo tipo di aggregazione è catturato nella funzione di ordine superiore List.fold e potrebbe essere scritto come List.fold (+) 0 xlist o addirittura ancora più semplicemente con la funzione di convenienza List.sum come solo List.sum xlist .
Ho usato la ricorsione pesantemente nel gioco giocando AI. Scrivendo in C ++, ho fatto uso di una serie di circa 7 funzioni che si richiamano l'una all'altra (con la prima funzione che ha un'opzione per ignorare tutte quelle e chiamare invece una catena di altre 2 funzioni). La funzione finale in entrambe le catene ha chiamato di nuovo la prima funzione fino a quando la profondità rimanente che volevo cercare andasse a 0, nel qual caso la funzione finale chiamerebbe la mia funzione di valutazione e restituire il punteggio della posizione.
Le molteplici funzioni mi hanno permesso di diramarti facilmente in base alle decisioni dei giocatori o agli eventi casuali del gioco. Farei uso del pass-by-reference ogni volta che potrei, perché stavo passando per strutture dati molto grandi, ma a causa di come il gioco era strutturato, era molto difficile avere una "mossa di annullamento" nella mia ricerca, quindi Userei il pass-by-value in alcune funzioni per mantenere invariati i miei dati originali. Per questo motivo, il passaggio a un approccio basato su loop anziché a un approccio ricorsivo si è dimostrato troppo difficile.
Puoi vedere uno schema di base di questo tipo di programma, vedi link
Un buon esempio di vita reale negli affari è qualcosa chiamato "Bill of Materials". Questo è il dato che rappresenta tutti i componenti che compongono un prodotto finito. Ad esempio, usiamo una bicicletta. Una bicicletta ha manubri, ruote, un telaio, ecc. E ciascuno di questi componenti può avere sub-componenti. per esempio, la Ruota può avere Raggi, uno stelo della valvola, ecc. In genere questi sono rappresentati in una struttura ad albero.
Ora per interrogare qualsiasi informazione aggregata sulla BOM o per modificare elementi in una DBA spesso si ricorre alla ricorsione.
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>();
}
E una chiamata ricorsiva di esempio ...
static int ComponentCount(BomPart part)
{
int subCount = 0;
foreach(BomPart p in part.Components)
subCount += ComponentCount(p);
return part.Quantity * Math.Max(1,subCount);
}
Ovviamente la classe BomPart avrebbe molti altri campi. Potrebbe essere necessario capire quanti componenti di plastica hai, quanto lavoro ci vuole per costruire una parte completa, ecc. Tutto ciò torna tuttavia all'utilità di Ricorsione su una struttura ad albero.
I rapporti di famiglia sono buoni esempi perché tutti li comprendono intuitivamente:
ancestor(joe, me) = (joe == me)
OR ancestor(joe, me.father)
OR ancestor(joe, me.mother);
Un pozzo di lavoro interno di ricorsione piuttosto inutile e tuttavia ricorsivo è ricorsivo strlen() :
size_t strlen( const char* str )
{
if( *str == 0 ) {
return 0;
}
return 1 + strlen( str + 1 );
}
Nessuna matematica - una funzione molto semplice. Ovviamente non lo implementerai ricorsivamente nella vita reale, ma è una buona dimostrazione di ricorsione.
Un altro problema di ricorsione nel mondo reale a cui gli studenti potrebbero fare riferimento è quello di creare il proprio crawler web che estrae le informazioni da un sito Web e segua tutti i collegamenti all'interno di quel sito (e tutti i link da tali collegamenti, ecc.).
Ho risolto un problema con un modello di cavaliere (su una scacchiera) usando un programma ricorsivo. Dovevi spostare il cavaliere in modo che toccasse ogni quadrato tranne alcuni quadrati segnati.
Semplicemente:
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.
Molti tipi di scenari di "think-ahead" possono essere elaborati testando le possibilità future in un albero come questo.
Leggi altre domande sui tag recursion