ricorsione

"Ciao, Amigo. Oggi Bilaabo ti parlerà della ricorsione."

Come sai, in Java alcuni metodi chiamano altri metodi. Inoltre, quando viene chiamato un metodo, gli vengono passati argomenti specifici, ma le variabili locali del metodo assumono determinati valori durante l'esecuzione.

"Uh Huh."

"E come sai, le variabili interne dei diversi metodi sono indipendenti l'una dall'altra."

"Uh Huh."

"Quindi immagina la situazione in cui un metodo chiama se stesso. Questo si chiama ricorsione. Ad esempio:"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

10
9
8
7
6
5
4
3
2
1
Boom!

"Vedo che il metodo chiama se stesso nel codice, ma onestamente non capisco cosa stia succedendo."

"Beh, più o meno la stessa cosa che accade quando viene chiamato un metodo diverso."

"No, sto chiedendo cosa succede con le variabili? Con i loro valori? E come si esce dal metodo? O si esce da tutto in una volta?"

"Santo cielo. È tutto molto più semplice. Immaginiamo che il metodo che richiama se stesso sia stato moltiplicato molte volte. Allora avremmo la situazione analoga:"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

public static void main(String[] args)
{
 countDown1(10);
}

public static void countDown1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown2(x - 1);
 }
}
public static void countDown2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown3(x - 1);
 }
}
public static void countDown3(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown4(x - 1);
 }
}

public static void countDown4(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown5(x - 1);
 }
}

3
2
1
Boom!

3
2
1
Boom!

"In altre parole, ogni volta che viene chiamato un metodo (anche da solo), vengono create nuove variabili che memorizzano i dati per questo metodo. Non ci sono variabili condivise."

"Ad ogni chiamata, viene creata in memoria un'altra copia degli argomenti del metodo, con nuovi valori. Quando ritorniamo al vecchio metodo, le sue variabili vengono utilizzate lì. In altre parole, durante la ricorsione in realtà chiamiamo un altro metodo, ma con il stesso codice nostro! "

"Capisco. E come funziona l'uscita da tali metodi? Forse un esempio?"

"OK. Un esempio vale più di mille parole. "Ecco il tuo esempio:"

public static void main(String[] args)
{
 print(3);
}

public static void print(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print(x - 1);
  System.out.println(x);
 }
}

public static void main(String[] args)
{
 print1(3);
}

public static void print1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print2(x - 1);
  System.out.println(x);
 }
}

public static void print2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print3(x - 1);
  System.out.println(x);
 }
}

…

3
2
1
Boom!
1
2
3

3
2
1
Boom!
1
2
3

"OK. Penso di aver capito. Perché abbiamo bisogno della ricorsione?"

"Ci sono molte, molte attività che possono essere suddivise in attività secondarie separate che sono identiche all'attività originale. Ad esempio, è necessario esaminare tutti gli elementi di un albero XML. Ogni elemento può avere diversi elementi figli e hanno i propri propri elementi figlio."

"Oppure devi visualizzare l'elenco dei file che si trovano in una directory e tutte le sue sottodirectory. Quindi scrivi un metodo che visualizza i file della directory corrente. Quindi per ottenere i file di tutte le sottodirectory, chiami il tuo metodo usando un argomento diverso: una sottodirectory."

"Per esempio:"

public static void main(String[] args)
{
 printAllFiles(new File("c:/windows/"));
}

public static void printAllFiles(File dir)
{
 for (File file : dir.listFiles())
 {
  if (file.isDirectory())
   printAllFiles(file);
  else
   System.out.println(file.getAbsolutePath());
 }
}

"Riga 8 – Otteniamo l'elenco di tutti i file (e le directory) nella directory dir."

"Righe 10-11 – Se il file è effettivamente una directory, richiamiamo printAllFiles , ma questa volta con un altro argomento: la sottodirectory."

"Riga 13 – Visualizziamo il nome del file corrente."

"OK. Penso di aver capito. Grazie, Bilaabo."