Svolgimento guidato


Potenze

Il metodo

Per scrivere un metodo ricorsivo si puo' ragionare cosi'. Vogliamo risolvere il problema su un input di taglia . Supponiamo di disporre di un “oracolo” che e' in grado di risolvere tutte le istanze del problema di taglia minore di . Non ci interessa sapere come funziona questo “oracolo”: l’importante sapere che funziona. Invochiamo opportunamente l’oracolo, otteniamo dei risultati, e li combiniamo per risolvere il problema di taglia .

Per esempio nel caso del metodo potenza supponiamo di disporre di un oracolo che calcoli le potenze con esponente minore di ; in particolare l’oracolo calcola le potenze con esponente (si riveda come e' definito nella pagina del problema). Consideriamo il caso di pari, dove . Per risolvere il problema e' sufficiente invocare l’oracolo, che ci restituira' il valore di , e moltiplicare tale valore per se stesso per ottenere :

int k = n/2;
double p = oracoloPotenza(x, k);
return p * p;

Ora entra in gioco la ricorsione: l’oracolo da invocare non e' altro che lo stesso metodo ricorsivo! Quindi il codice del caso pari diventa semplicemente:

int k = n/2;
double p = potenza(x, k);
return p * p;

Considerando tutti e tre i casi ( (caso base della ricorsione), dispari e pari) otteniamo il codice seguente:

public static double potenza(double x, int n) {
    if(n==0) return 1;
    else if(n%2 == 0) { //Se n e' pari
      int k = n/2;
      double p = potenza(x, k);
      return p*p;
    } else { //n dispari
      int k = n/2;  //Quoziente della divisione di n per 2
      double p = potenza(x, k);
      return p*p*x;      
    }
  }

Analisi del costo

Ogni attivazione del metodo potenza ha, di per se', costo costante (non ci sono cicli). Contiamo dunque quante volte il metodo viene attivato in conseguenza alla chiamata potenza(x, n), in funzione di n.

Osserviamo che nel corso di ogni chiamata in cui si ha un’attivazione ricorsiva del metodo, con input .
Quindi l’input delle varie attivazioni sara' rispettivamente (non superiore a) .

Ci fermeremo sicuramente quando l’input e' diventato minore di 1 (perche' allora sara' eseguito il caso base). Poiche' nell’-esima attivazioni l’input vale non piu' di , si ha che per , ossia per . Cio' significa che dopo attivazioni si sara' raggiunto il caso base. Il costo e' dunque .

Per finire, osserviamo che, essendo l’input un numero intero (), la dimensione di e' data dal numero di bit richiesti per la rappresentazione (binaria) di . Indichiamo tale numero con : si ha che , ossia . Introducendo tale valore nel costo precedentemente determinato otteniamo il costo in funzione della dimensione dell’input: (costo lineare nel numero dei bit).

Permutazioni

E’ possibile usare la ricorsione nel seguente modo. Si consideri l’array di input arr come un insieme. Per risolvere il problema con dimensione n, fissiamo in tutti i modi possibili il primo elemento dell’array: una volta fissato il primo elemento, si trattera’ di permutare, in tutti i modi possibili, i restanti n-1 elementi. Abbiamo dunque un problema di dimensione n-1: siamo in grado di usare l’oracolo ricorsivo per trovare le permutazioni di tali elementi.