Uno dei modi migliori per imparare la ricorsione è quello di acquisire esperienza in un linguaggio di programmazione funzionale come Haskell o Lisp o Scheme.
Quindi trovare i problemi ricorsivi può essere ridotto alla ricerca di alcuni problemi e risposte relative ai linguaggi di programmazione funzionale. Ecco un esempio 99 lisp problems.
Ci vogliono davvero solo 5 minuti per apprendere Scheme o Lisp in modo da poter iniziare subito con degli esempi per il test che hai menzionato domani.
Un altro ottimo modo per imparare la ricorsione è quello di ottenere un po 'di pratica in prove matematiche che coinvolgono l'induzione.
I concetti chiave relativi alla ricorsione:
Con la ricorsione non hai bisogno di sapere come risolvere il problema. Hai solo bisogno di sapere 2 cose. 1) come risolvere la più piccola istanza del problema e 2) come suddividerla in parti più piccole.
Equivalentemente, è sufficiente tenere presente che è necessario: 1) un caso base e 2) un caso ricorsivo.
Il caso base gestisce 1 singola istanza di ciò che si desidera fare con il più piccolo input.
Il caso ricorsivo suddivide il problema in un sottoproblema. Alla fine questo sottoproblema si ridurrà al caso base.
Esempio:
//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
if(x == 0) //base case
return 0;
else
return sumAll(x-1) + x; //recursive case
}
È importante comprendere che il caso base non è difficile capire. Deve solo esistere. Ecco una soluzione equivalente per x> 0:
//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
if(x == 1) //base case
return 1;
else
return sumAll(x-1) + x; //recursive case
}
fonte
2009-03-11 15:11:55
Dannazione, stavo per fare lo scherzo ricorsivo della ricorsione, ma vedo che è la prima risposta al thread collegato. –
C'è un vecchio detto: "Per comprendere la ricorsione, aiuta a capire la ricorsione." –
La sintassi del linguaggio di programmazione è indipendente dalla comprensione della ricorsione stessa. Si prega di considerare le lingue funzionali. –