Java Languagericorsione


introduzione

La ricorsione si verifica quando un metodo chiama se stesso. Un tale metodo è chiamato ricorsivo . Un metodo ricorsivo può essere più conciso di un approccio non ricorsivo equivalente. Tuttavia, per una ricorsione profonda, a volte una soluzione iterativa può consumare meno spazio di stack finito di un thread.

Questo argomento include esempi di ricorsione in Java.

Osservazioni

Progettare un metodo ricorsivo

Quando si progetta un metodo ricorsivo, tenere presente che è necessario:

  • Caso base. Questo definirà quando la tua ricorsione si fermerà e produrrà il risultato. Il caso base nell'esempio fattoriale è:

    if (n <= 1) {
        return 1;
    }
    
  • Chiamata ricorsiva. In questa affermazione si richiama il metodo con un parametro modificato. La chiamata ricorsiva nell'esempio fattoriale sopra è:

    else {
        return n * factorial(n - 1);
    }
    

Produzione

In questo esempio si calcola il numero fattoriale n-esimo. I primi fattoriali sono:

0! = 1

1! = 1

2! = 1 x 2 = 2

3! = 1 x 2 x 3 = 6

4! = 1 x 2 x 3 x 4 = 24

...


Eliminazione di Java e Tail-call

I compilatori Java attuali (fino a Java 9 incluso) non eseguono l'eliminazione di tail-call. Questo può influire sulle prestazioni degli algoritmi ricorsivi e, se la ricorsione è abbastanza profonda, può portare a crash di StackOverflowError ; vedere La ricorsione profonda è problematica in Java

ricorsione Esempi correlati