Informatica I - la ricorsione multipla

Ricorsione multipla

Quando un metodo invoca se stesso più volte durante la propria esecuzione.

Esempio: il calcolo dei numeri di Fibonacci

Soluzione ricorsiva

Esempio:

public static long recursiveFib(int n) {
    if (n < 1) throw new IllegalArgumentException();
    System.out.println("Inizio recursiveFib(" + n + ")");
    invcount++;
    long f;
    if (n < 3) f = 1;
    else f = recursiveFib(n-1) + recursiveFib(n-2);
    System.out.println("Uscita recursiveFib(" + n + ")");
    return f;
}

Soluzione iterativa

Esempio:

public static long iterativeFib(int n) {
    if (n < 1) throw new IllegalArgumentException();
    long f = 1;
    if (n >= 3) {
        long fib1 = 1;
        long fib2 = 1;
        for (int i = 3; i <= n; i++) {
            f = fib1 + fib2;
            fib2 = fib1;
            fib1 = f;
        }
    }
    return f;
}

Considerazioni sulla ricorsione multipla

Il metodo Fib realizza una ricorsione multipla. La ricorsione multipla va usata con molta attenzione perché può portare a programmi molto inefficienti. Eseguendo il calcolo dei numeri di Fibonacci di ordine crescente si nota che il tempo di elaborazione cresce molto rapidamente (Sono necessarie quasi 3 milioni di invocazioni per calcolare Fib(31)!). Invece, una soluzione iterativa risulta molto più efficiente.