Quali sono i casi d'uso della ricorsione?

La ricorsione è un meraviglioso strumento di programmazione. Fornisce un modo semplice e potente di affrontare una varietà di problemi. È spesso difficile, tuttavia, vedere come un problema può essere affrontato ricorsivamente; può essere difficile "pensare" ricorsivamente. È anche facile scrivere un programma ricorsivo che richiede troppo tempo per essere eseguito o che non termina affatto correttamente. In questo articolo andremo oltre le basi della ricorsione e speriamo di aiutarvi a sviluppare, o perfezionare, un'abilità di programmazione molto importante.

Che cos'è la ricorsione?

Per poter dire esattamente cos'è la ricorsione, dobbiamo prima rispondere a "Cos'è la ricorsione? Fondamentalmente, si dice che una funzione è ricorsiva se chiama se stessa. Below is pseudocode for a recursive function that prints the phrase "Hello World" a total ofcount times:

1. function HelloWorld(count) {  
2. if(count<1) 
3. return print("Hello World!"); 
4. HelloWorld(count - 1); 
5. } 

Potrebbe non essere immediatamente chiaro cosa stiamo facendo qui - quindi seguiamo cosa succede se chiamiamo la nostra funzione con il conteggio impostato a 10. Poiché il conteggio non è inferiore a 1, non facciamo nulla nella prima riga. Sulla successiva, stampiamo una volta "Hello World! A questo punto dobbiamo stampare la nostra frase altre 9 volte. Dato che ora abbiamo una funzione HelloWorld che può fare proprio questo, chiamiamo semplicemente HelloWorld (questa volta con count impostato a 9) per stampare le copie rimanenti. Quella copia di HelloWorld stamperà la frase una volta, e poi chiamerà un'altra copia di HelloWorld per stampare le 8 rimanenti. Questo continuerà fino a quando alla fine chiameremo HelloWorld con il conteggio impostato a zero. HelloWorld(0) non fa nulla; semplicemente ritorna. Una volta che HelloWorld(0) ha finito, anche HelloWorld(1) ha finito, e ritorna. Questo continua fino alla nostra chiamata originale di HelloWorld(10), che termina l'esecuzione avendo stampato un totale di 10 "Hello World!"

Potreste pensare che questo non sia terribilmente eccitante, ma questa funzione dimostra alcune considerazioni chiave nella progettazione di un algoritmo ricorsivo:

1. Gestisce un semplice "caso base" senza usare la ricorsione.
   In questo esempio, il caso base è "HelloWorld(0)"; se alla funzione viene chiesto di stampare zero volte, allora ritorna senza generare altri "HelloWorld".
2. Evita i cicli.
   Immaginate se "HelloWorld(10)" chiamasse "HelloWorld(10)" che chiama "HelloWorld(10)". Vi ritrovereste con un ciclo infinito di chiamate, e questo di solito risulterebbe in un errore di "stack overflow" durante l'esecuzione. In molti programmi ricorsivi, potete evitare i cicli avendo ogni chiamata di funzione per un problema che è in qualche modo più piccolo o più semplice del problema originale. In questo caso, per esempio, il conteggio sarà sempre più piccolo ad ogni chiamata. Man mano che il problema diventa sempre più semplice (in questo caso, considereremo "più semplice" stampare qualcosa zero volte piuttosto che stamparlo 5 volte) alla fine si arriverà al "caso base" e si smetterà di ricorrere. Ci sono molti modi per evitare cicli infiniti, ma assicurarsi di avere a che fare con problemi progressivamente più piccoli o più semplici è una buona regola empirica.
3. Ogni chiamata della funzione rappresenta una gestione completa del compito dato.
   A volte la ricorsione può sembrare un po' magica nel modo in cui scompone grandi problemi. Tuttavia, non esistono cose come un pranzo gratis. Quando alla nostra funzione viene dato un argomento di 10, stampiamo "Hello World!" una volta e poi lo stampiamo altre 9 volte. We can pass a part of the job along to a recursive call, but the original function still has to account for all 10 copies somehow.

Check out use case scenarios at http://www.daqwest.com/quests/26....

1) Hierarchies, Networks, or Graphs

2) Multiple Related Decisions

3) Explicit Recursive Relationships

Good luck !!!