Ricorsione in Java

1. Introduzione

In questo articolo, ci concentreremo su un concetto fondamentale in qualsiasi linguaggio di programmazione: la ricorsione.

Spiegheremo le caratteristiche di una funzione ricorsiva e mostreremo come usare la ricorsione per risolvere vari problemi in Java.

2. Comprendere la ricorsione

2.1. La definizione

In Java, il meccanismo di chiamata di funzione supporta la possibilità di avere una chiamata di metodo stesso . Questa funzionalità è nota come ricorsione .

Ad esempio, supponiamo di voler sommare gli interi da 0 a un valore n :

public int sum(int n) { if (n >= 1) { return sum(n - 1) + n; } return n; }

Ci sono due requisiti principali di una funzione ricorsiva:

  • A Stop Condition - la funzione restituisce un valore quando una certa condizione è soddisfatta, senza un'ulteriore chiamata ricorsiva
  • La chiamata ricorsiva : la funzione chiama se stessa con un input che è un passo più vicino alla condizione di arresto

Ogni chiamata ricorsiva aggiungerà un nuovo frame alla memoria dello stack della JVM. Quindi, se non prestiamo attenzione a quanto in profondità la nostra chiamata ricorsiva può immergersi, potrebbe verificarsi un'eccezione di memoria esaurita.

Questo potenziale problema può essere evitato sfruttando l'ottimizzazione della ricorsione della coda.

2.2. Ricorsione della coda contro ricorsione della testa

Ci riferiamo a una funzione ricorsiva come ricorsione in coda quando la chiamata ricorsiva è l'ultima cosa che la funzione esegue. Altrimenti, è noto come ricorsione della testa .

La nostra implementazione sopra della funzione sum () è un esempio di ricorsione della testa e può essere modificata in ricorsione della coda:

public int tailSum(int currentSum, int n) { if (n <= 1) { return currentSum + n; } return tailSum(currentSum + n, n - 1); }

Con la ricorsione in coda, la chiamata ricorsiva è l'ultima cosa che fa il metodo, quindi non c'è più niente da eseguire all'interno della funzione corrente.

Pertanto, logicamente non è necessario memorizzare lo stack frame della funzione corrente.

Sebbene il compilatore possa utilizzare questo punto per ottimizzare la memoria, va notato che il compilatore Java non ottimizza per ora la ricorsione in coda .

2.3. Ricorsione contro iterazione

La ricorsione può aiutare a semplificare l'implementazione di alcuni problemi complicati rendendo il codice più chiaro e leggibile.

Ma come abbiamo già visto l'approccio ricorsivo spesso richiede più memoria poiché la memoria dello stack richiesta aumenta con ogni chiamata ricorsiva.

In alternativa, se possiamo risolvere un problema con la ricorsione, possiamo anche risolverlo per iterazione.

Ad esempio, il nostro metodo di somma potrebbe essere implementato utilizzando l'iterazione:

public int iterativeSum(int n) { int sum = 0; if(n < 0) { return -1; } for(int i=0; i<=n; i++) { sum += i; } return sum; }

Rispetto alla ricorsione, l'approccio iterativo potrebbe potenzialmente fornire prestazioni migliori. Detto questo, l'iterazione sarà più complicata e più difficile da capire rispetto alla ricorsione, ad esempio: attraversare un albero binario.

Fare la scelta giusta tra ricorsione della testa, ricorsione della coda e un approccio iterativo dipende tutto dal problema e dalla situazione specifici.

3. Esempi

Proviamo ora a risolvere alcuni problemi in modo ricorsivo.

3.1. Trovare N-esima potenza di dieci

Supponiamo di dover calcolare la n -esima potenza di 10. Qui il nostro input è n. Pensando in modo ricorsivo, possiamo calcolare prima (n-1) -esima potenza di 10 e moltiplicare il risultato per 10.

Quindi, per calcolare la (n-1) -esima potenza di 10 sarà la (n-2) -esima potenza di 10 e moltiplicare il risultato per 10, e così via. Continueremo in questo modo finché non arriveremo al punto in cui dobbiamo calcolare la (nn) -esima potenza di 10, che è 1.

Se volessimo implementarlo in Java, scriveremmo:

public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10; }

3.2. Trovare l'elemento N-esimo della sequenza di Fibonacci

A partire da 0 e 1 , la sequenza di Fibonacci è una sequenza di numeri in cui ogni numero è definito come la somma dei due numeri che la precedono : 0 1 1 2 3 5 8 13 21 34 55 ...

Quindi, dato un numero n , il nostro problema è trovare l' n -esimo elemento della sequenza di Fibonacci . Per implementare una soluzione ricorsiva, abbiamo bisogno di capire la condizione di stop e la chiamata ricorsiva .

Fortunatamente, è davvero semplice.

Chiamiamo f (n) l' n -esimo valore della sequenza. Allora avremo f (n) = f (n-1) + f (n-2) (la chiamata ricorsiva ) .

Nel frattempo, f (0) = 0 e f (1) = 1 ( condizione di arresto) .

Quindi, è davvero ovvio per noi definire un metodo ricorsivo per risolvere il problema:

public int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); }

3.3. Conversione da decimale a binario

Consideriamo ora il problema di convertire un numero decimale in binario. Il requisito è implementare un metodo che riceva un valore intero positivo n e restituisca una rappresentazione String binaria .

Un approccio per convertire un numero decimale in binario consiste nel dividere il valore per 2, registrare il resto e continuare a dividere il quoziente per 2.

Continuiamo a dividere in questo modo finché non otteniamo un quoziente di 0 . Quindi, scrivendo tutti i resti in ordine di riserva, otteniamo la stringa binaria.

Quindi, il nostro problema è scrivere un metodo che restituisca questi resti in ordine di riserva:

public String toBinary(int n) { if (n <= 1 ) { return String.valueOf(n); } return toBinary(n / 2) + String.valueOf(n % 2); }

3.4. Altezza di un albero binario

L'altezza di un albero binario è definita come il numero di bordi dalla radice alla foglia più profonda. Il nostro problema ora è calcolare questo valore per un dato albero binario.

Un approccio semplice sarebbe quello di trovare la foglia più profonda, quindi contare i bordi tra la radice e quella foglia.

Ma provando a pensare a una soluzione ricorsiva, possiamo riformulare la definizione per l'altezza di un albero binario come l'altezza massima del ramo sinistro della radice e del ramo destro della radice, più 1 .

Se la radice non ha un ramo sinistro e uno destro, la sua altezza è zero .

Ecco la nostra implementazione:

public int calculateTreeHeight(BinaryNode root){ if (root!= null) { if (root.getLeft() != null || root.getRight() != null) { return 1 + max(calculateTreeHeight(root.left), calculateTreeHeight(root.right)); } } return 0; }

Quindi, vediamo che alcuni problemi possono essere risolti con la ricorsione in un modo davvero semplice.

4. Conclusione

In questo tutorial, abbiamo introdotto il concetto di ricorsione in Java e lo abbiamo dimostrato con alcuni semplici esempi.

L'implementazione di questo articolo può essere trovata su Github.