ricorsione Java

ricorsione Java

La ricorsione è la tecnica per effettuare una chiamata di funzione stessa. Questa tecnica fornisce un modo per scomporre problemi complicati in problemi semplici che sono più facili da risolvere.

La ricorsione può essere un po' difficile da capire. Il modo migliore per capire come funziona è sperimentarlo.

Esempio di ricorsione

Sommare due numeri insieme è facile, ma aggiungere un intervallo di numeri è più complicato. Nell'esempio seguente, la ricorsione viene utilizzata per sommare un intervallo di numeri scomponendolo nel semplice compito di sommare due numeri:

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Esempio spiegato

Quando la sum()funzione viene chiamata, aggiunge il parametro kalla somma di tutti i numeri inferiori a ke restituisce il risultato. Quando k diventa 0, la funzione restituisce solo 0. Durante l'esecuzione, il programma segue questi passaggi:

Poiché la funzione non chiama se stessa quando kè 0, il programma si ferma lì e restituisce il risultato.

Condizione di arresto

Proprio come i loop possono incorrere nel problema del loop infinito, le funzioni ricorsive possono incorrere nel problema della ricorsione infinita. La ricorsione infinita è quando la funzione non smette mai di chiamare se stessa. Ogni funzione ricorsiva dovrebbe avere una condizione di arresto, che è la condizione in cui la funzione smette di chiamare se stessa. Nell'esempio precedente, la condizione di arresto è quando il parametro kdiventa 0.

È utile vedere una varietà di esempi diversi per comprendere meglio il concetto. In questo esempio, la funzione aggiunge un intervallo di numeri tra un inizio e una fine. La condizione di arresto per questa funzione ricorsiva è quando fine non è maggiore di inizio :

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}