Java Language
ricorsione

introduzione

Osservazioni

L'idea di base della ricorsione

Cos'è la ricorsione:

In generale, la ricorsione è quando una funzione invoca se stessa, direttamente o indirettamente. Per esempio:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Condizioni per l'applicazione della ricorsione a un problema:

Esistono due presupposti per l'utilizzo di funzioni ricorsive per risolvere un problema specifico:

1. Ci deve essere una condizione di base per il problema, che sarà l'endpoint per la ricorsione. Quando una funzione ricorsiva raggiunge la condizione di base, non effettua ulteriori chiamate (più profonde) ricorsive.

2. Ogni livello di ricorsione dovrebbe tentare un problema più piccolo. La funzione ricorsiva divide così il problema in parti sempre più piccole. Supponendo che il problema sia finito, ciò garantirà la terminazione della ricorsione.

In Java c'è una terza precondizione: non dovrebbe essere necessario recidare troppo profondamente per risolvere il problema; vedere La ricorsione profonda è problematica in Java

Esempio

La seguente funzione calcola i fattoriali usando la ricorsione. Si noti come il metodo factorial chiama all'interno della funzione. Ogni volta che chiama se stesso, riduce il parametro n di 1. Quando n raggiunge 1 (condizione di base), la funzione non verrà eseguita più in profondità.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{Questo non è un modo pratico di calcolare i fattoriali in Java, dal momento che non prende in considerazione l'overflow dei numeri interi o l'overflow dello stack delle chiamate (ad esempio le eccezioni StackOverflowError ) per i grandi valori di n .}

Calcolo del numero dell'N ° Fibonacci

Il seguente metodo calcola il numero Nth Fibonacci usando la ricorsione.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

Il metodo implementa un caso base (n <= 2) e un caso ricorsivo (n> 2). Questo illustra l'uso della ricorsione per calcolare una relazione ricorsiva.

Tuttavia, sebbene questo esempio sia illustrativo, è anche inefficiente: ogni singola istanza del metodo chiamerà la funzione stessa due volte, portando ad una crescita esponenziale nel numero di volte in cui la funzione viene chiamata con l'aumentare di N. La funzione precedente è O (2 ^N ), ma una soluzione iterativa equivalente ha complessità O (N). Inoltre, esiste un'espressione "forma chiusa" che può essere valutata nelle moltiplicazioni in virgola mobile O (N).

Calcolo della somma di numeri interi da 1 a N

Il seguente metodo calcola la somma di interi da 0 a N usando la ricorsione.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

Questo metodo è O (N) e può essere ridotto a un ciclo semplice mediante l'ottimizzazione della coda di chiamata. Infatti esiste un'espressione di forma chiusa che calcola la somma in operazioni O(1) .

Calcolare l'ennesima potenza di un numero

Il seguente metodo calcola il valore di num elevato alla potenza di exp utilizzando la ricorsione:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

Questo illustra i principi sopra menzionati: il metodo ricorsivo implementa un caso base (due casi, n = 0 e n = 1) che termina la ricorsione e un caso ricorsivo che chiama di nuovo il metodo. Questo metodo è O (N) e può essere ridotto a un ciclo semplice mediante l'ottimizzazione della coda di chiamata.

Invertire una stringa usando Ricorsione

Di seguito è riportato un codice ricorsivo per invertire una stringa

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

Attraversare una struttura dati Albero con ricorsione

Considera la classe Node con 3 dati membri, il puntatore figlio sinistro e il puntatore figlio destro come sotto.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

Possiamo attraversare l'albero costruito collegando più oggetti della classe Node come di seguito, l'attraversamento è chiamato attraversamento in ordine dell'albero.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

Come dimostrato sopra, usando la ricorsione possiamo attraversare la struttura dei dati dell'albero senza utilizzare altre strutture dati che non sono possibili con l'approccio iterativo .

Tipi di ricorsione

La ricorsione può essere classificata come ricorsione della testa o ricorsione della coda , a seconda di dove viene collocata la chiamata al metodo ricorsivo.

Nella ricorsione della testa , la chiamata ricorsiva, quando accade, viene prima di un'altra elaborazione nella funzione (pensate che avvenga in alto, o in testa, della funzione).

Nella ricorsione di coda , è l'opposto: l'elaborazione avviene prima della chiamata ricorsiva. Scegliere tra i due stili ricorsivi può sembrare arbitrario, ma la scelta può fare la differenza.

Una funzione con un percorso con una singola chiamata ricorsiva all'inizio del percorso utilizza quella che viene chiamata ricorsione della testa. La funzione fattoriale di una mostra precedente utilizza la ricorsione della testa. La prima cosa che fa una volta che determina che la ricorsione è necessaria è chiamarsi con il parametro decrementato. Una funzione con una singola chiamata ricorsiva alla fine di un percorso utilizza la ricorsione della coda.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

Se la chiamata ricorsiva si verifica alla fine di un metodo, viene chiamata tail recursion . La ricorsione della coda è similar to a loop . Il method executes all the statements before jumping into the next recursive call .

Se la chiamata ricorsiva si verifica beginning of a method, it is called a head recursion . Il method saves the state before jumping into the next recursive call .

Riferimento: la differenza tra ricorsione testa e coda

StackOverflowError e ricorsione in loop

Se una chiamata ricorsiva diventa "troppo profonda", ciò provoca un StackOverflowError . Java assegna un nuovo frame per ogni chiamata di metodo sullo stack del suo thread. Tuttavia, lo spazio della pila di ciascun thread è limitato. Troppi frame sullo stack portano allo Stack Overflow (SO).

Esempio

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

Chiamare questo metodo con parametri di grandi dimensioni (es. recursion(50000) probabilmente si tradurrà in un overflow dello stack. Il valore esatto dipende dalla dimensione dello stack di thread, che a sua volta dipende dalla costruzione del thread, dai parametri della riga di comando come -Xss o dal dimensione predefinita per JVM.

Soluzione

Una ricorsione può essere convertita in un ciclo memorizzando i dati per ogni chiamata ricorsiva in una struttura dati. Questa struttura di dati può essere archiviata nell'heap anziché nella pila di thread.

In generale, i dati necessari per ripristinare lo stato di un'invocazione di metodo possono essere memorizzati in uno stack e un ciclo while può essere utilizzato per "simulare" le chiamate ricorsive. I dati che possono essere richiesti includono:

• l'oggetto per cui è stato chiamato il metodo (solo i metodi di istanza)
• i parametri del metodo
• variabili locali
• la posizione corrente nell'esecuzione o il metodo

Esempio

La seguente classe consente la ricorsività di una struttura ad albero che stampa fino ad una profondità specificata.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

per esempio

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

stampe

(((...)20(...))10((...)30))

Questo potrebbe essere convertito nel seguente ciclo:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

Nota: questo è solo un esempio dell'approccio generale. Spesso puoi trovare un modo molto migliore per rappresentare un frame e / o memorizzare i dati del frame.

La ricorsione profonda è problematica in Java

Considera il seguente metodo ingenuo per aggiungere due numeri positivi usando la ricorsione:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

Questo è algoritmicamente corretto, ma ha un grosso problema. Se si chiama add a large a , si bloccherà con StackOverflowError , su qualsiasi versione di Java fino a (almeno) Java 9.

In un tipico linguaggio di programmazione funzionale (e in molti altri linguaggi) il compilatore ottimizza la ricorsione della coda . Il compilatore noterebbe che la chiamata da add (sulla linea taggata) è una chiamata di coda e riscriverebbe efficacemente la ricorsione come un ciclo. Questa trasformazione è chiamata eliminazione di coda.

Tuttavia, i compilatori Java di generazione corrente non eseguono l'eliminazione delle chiamate tail. (Questa non è una semplice svista, ci sono sostanziali motivi tecnici per questo, vedi sotto). Invece, ogni chiamata ricorsiva di add fa sì che un nuovo frame venga allocato nello stack del thread. Ad esempio, se si chiama add(1000, 1) , occorreranno 1000 chiamate ricorsive per arrivare alla risposta 1001 .

Il problema è che la dimensione dello stack di thread Java è fissa quando viene creato il thread. (Ciò include il thread "principale" in un programma a thread singolo.) Se vengono allocati troppi frame di stack, lo stack andrà in overflow. La JVM lo rileva e lancia un StackOverflowError .

Un approccio per affrontare questo è semplicemente utilizzare uno stack più grande. Esistono opzioni JVM che controllano la dimensione predefinita di uno stack e puoi anche specificare la dimensione dello stack come parametro del costruttore di Thread . Sfortunatamente, questo "mette fuori" solo l'overflow dello stack. Se è necessario eseguire un calcolo che richiede uno stack ancora più grande, viene restituito StackOverflowError .

La vera soluzione consiste nell'identificare algoritmi ricorsivi in ​​cui è probabile una ricorsione profonda e eseguire manualmente l'ottimizzazione della coda di chiamata a livello di codice sorgente. Ad esempio, il nostro metodo add può essere riscritto come segue:

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(Ovviamente, ci sono modi migliori per aggiungere due numeri interi. Quanto sopra è semplicemente per illustrare l'effetto dell'eliminazione manuale della coda di chiamata.)

Perché l'eliminazione tail-call non è implementata in Java (ancora)

Ci sono una serie di motivi per cui l'aggiunta dell'eliminazione delle chiamate tail a Java non è facile. Per esempio:

• Alcuni codici potrebbero fare affidamento su StackOverflowError per (ad esempio) posizionare un limite sulla dimensione di un problema computazionale.
• I responsabili della sicurezza di Sandbox si affidano spesso all'analisi dello stack di chiamate quando decidono se consentire al codice non privilegiato di eseguire un'azione privilegiata.

Come spiega John Rose in "Tail calls in the VM" :

"Gli effetti della rimozione del frame dello stack del chiamante sono visibili per alcune API, in particolare per i controlli di controllo degli accessi e per la traccia dello stack, come se il chiamante avesse chiamato direttamente il callee.Tutti i privilegi posseduti dal chiamante vengono eliminati dopo che il controllo è stato trasferito al tuttavia, il collegamento e l'accessibilità del metodo del callee sono calcolati prima del trasferimento del controllo e tengono conto del chiamante di coda. "

In altre parole, l'eliminazione di chiamata di coda potrebbe far sì che un metodo di controllo degli accessi ritenga erroneamente che un'API sensibile alla sicurezza sia stata chiamata da codice attendibile.