Ricorsione

Due concetti essenziali:

cosa succede quando si invoca un metodo ricorsivo

record di attivazione, sequenza di invocazioni

come si scrivono metodi ricorsivi

assunzione ricorsiva, caso base

Record di attivazione

Ogni volta che si invoca un metodo:

		// definizione del metodo
  static int inutile(int a, String b) {
    double x;
    ...
    return 0;
  }
		// invocazione del metodo
  y=inutile(2, "abcd");

• si crea una zona di memoria che contiene sia i parametri formali che le variabili locali (es. un intero a e una stringa b, e poi un reale x)
• i dati passati come argomenti vengono copiati nei parametri formali (es. 2 viene messo in a mentre "abcd" viene messo in b)
• si esegue il corpo del metodo
• il valore di ritorno viene usato come se fosse scritto al posto della invocazione

Record di attivazione: contiene le variabili (locali+parametri formali) di una invocazione di metodo.

Metodo che invoca un altro metodo

I metodi possono avere variabili con lo stesso nome

Sono variabili diverse (in record di attivazione diversi)

static void primo(int i) {
  double j;
  secondo("stringa");
}

static void secondo(String i) {
  int j;
}

int i
double j

String i
int j

Per ogni metodo, ho un record di attivazione.

Il record di un metodo contiene le sue variabili locali e i suoi parametri formali.

Invocare due volte un metodo

Se in un programma invoco due volte un metodo:

static void primo() {
  int i;
  ...
}

...main(...) {
int x;

primo();
primo();

• alla prima invocazione, si crea un record di attivazione:

  int x	main
  int i	primo

• quando termina, viene distrutto

  int x

  main

• alla seconda invocazione, si crea un altro record,

  int x	main
  int i	primo

• che viene cancellato alla fine dell'esecuzione del metodo

  int x

  main

In questo caso, in ogni momento al massimo c'è un record di attivazione di primo in memoria

Se invoco metodi in sequenza, è sempre cosí

Ricorsione

Un metodo può anche invocare se stesso.

  static void ricorsivo(int i) {
    int j=i+1;
    System.out.println(i);
    ricorsivo(j);
  }

Cosa succede quando un metodo invoca se stesso?

Ogni volta che si invoca un metodo, viene creato un record di attivazione

Vale anche quando un metodo invoca se stesso: ogni volta, ho un nuovo record di attivazione

I record di attivazione dell'esempio

• prima chiamata: ho un record che contiene due interi i e j
• seconda chiamata: ho un secondo record che contiene i e j
• ecc.

Attenzione: le due i sono due variabili completamente diverse! Lo stesso per le due j.

Le due i devono necessariamente avere lo stesso tipo (sono definite nello stesso modo). Ma sono variabili diverse. Lo stesso per le due j.

Esercizio

Quali sono i record di attivazione del metodo di sopra quanto viene invocato ricorsivo(3)?

  static void ricorsivo(int i) {
    int j=i+1;
    System.out.println(i);
    ricorsivo(j);
  }

Soluzione

Prima invocazione:

i=3;
j=indefinito;

Viene alterato il valore di j:

i=3;
j=4;

Viene stampato i (stampo 3)

Seconda invocazione

Al metodo viene passato il valore di j, ossia 4.

• si crea un altro record di attivazione
• questo record contiene altre variabili i e j
• nella i viene inizialmente messo il valore passato come parametro (4)

i=3;
j=4;

i=4;
j=indefinito;

Il metodo viene ora eseguito

Nel corpo del metodo, quando uso i e j queste sono le variabili del nuovo record di attivazione (quello creato apposta per questa attivazione)

Continua

Si esegue il corpo del metodo, si mette 5 in j e si stampa i (vale 4).

i=3;
j=4;

i=4;
j=5;

Si fa riferimento alle variabili i e j del record creato per questa invocazione.

Continua

Si fa una nuova invocazione ricorsiva:

i=3;
j=4;

i=4;
j=5;

i=5;
j=indefinito;

Eccetera.

Si continua all'infinito.

Metodi ricorsivi senza terminazione:
alla fine, esauriscono la memoria.

Iterazione e ricorsione

Il metodo ricorsivo senza terminazione permette di realizzare un ciclo infinito

Dato che ricorsivo(j) mette nel parametro formale (i) il valore del parametro attuale (j), un ciclo equivalente è:

  while(true) {
    j=i+1;
    System.out.println(i);
    i=j;
  }

La ricorsione permette di ripetere istruzioni

È quindi una forma di ciclo.

C'è una differenza importante

Differenza ciclo-ricorsione

// iterazione
  while(true) {
    j=i+1;
    System.out.println(i);
    i=j;
  }
// ricorsione
  static void ricorsivo(int i) {
    int j=i+1;
    System.out.println(i);
    ricorsivo(j);
  }

ciclo

ho sempre le stesse due variabili i e j

ricorsione

ad ogni chiamata ricorsiva ho una variabile i diversa dalle altre; lo stesso per j.

Terminazione dei metodi ricorsivi

Il metodo deve, prima o poi, smettere di invocarsi

Questo fa terminare l'esecuzione

  static void ricorsivo(int i) {
    int j=i+1;
    System.out.println(i);
    if(i<5)
      ricorsivo(j);
  }

Quando i raggiunge 5, il metodo termina senza invocare se stesso

Terminazione di un metodo ricorsivo

Cosa succede quando il metodo non si invoca?

Stessa regola di tutti gli altri metodi: si elimina il record di attivazione e si riprende da dove si era lasciato.

Prima invocazione:

i=3;
j=indef;

Seconda invocazione:

i=3;
j=4;

i=4;
j=indef;

Terza invocazione:

i=3;
j=4;

i=4;
j=5;

i=5;
j=indef;

In j viene messo 6, ma non viene più fatta la invocazione ricorsiva, dato che i<5 è falso.

L'esecuzione del metodo termina perchè non ci sono altre istruzioni.

Viene quindi cancellato il record di attivazione, e si riparte da dove si era lasciato:

i=3;
j=4;

i=4;
j=5;

Si era lasciato il metodo ricorsivo per invocare ricorsivo. Dato che non ci sono altre istruzioni, si termina anche questo.

i=3;
j=4;

Termina anche questa chiamata.

Ricorsione: interpretazione con metodi diversi

Quando ho un metodo ricorsivo, posso pensare di avere più copie dello stesso metodo, con nomi diversi:

• ricorsivo invoca ricorsivo1
• ricorsivo1 invoca ricorsivo2
• ricorsivo2 invoca ricorsivo3
• ecc.

  static void ricorsivo(int i) {
    int j=i+1;
    System.out.println(i);
    if(i<5)
      ricorsivo1(j);
  }

  static void ricorsivo1(int i) {
    int j=i+1;
    System.out.println(i);
    if(i<5)
      ricorsivo2(j);
  }

  static void ricorsivo2(int i) {
    int j=i+1;
    System.out.println(i);
    if(i<5)
      ricorsivo3(j);
  }

Quando ricorsivo2 termina, si riprende dal punto di ricorsivo1 in cui si trova la invocazione di ricorsivo2

Attenzione: pensare a più metodi serve solo a capire come funziona la ricorsione.

In pratica, non so quanti metodi dovrei definire (es, se faccio ricorsivo(-10) mi servono quindici metodi, per ricorsivo(-20) ne servono venticinque)

Cicli definiti e ricorsione

Con la ricorsione posso simulare cicli definiti:

for(i=0; i<10; i++)
  System.out.println(i);

Devo eseguire la stessa istruzione per dieci volte:

static void stampadieci(int i) {
  if(i<10) {
    System.out.println(i);
    i++;
    stampadieci(i);
  }
}

Invocazione: stampadieci(0)

Attenzione: si può anche scrivere:

static void stampadieci(int i) {
  if(i<10) {
    System.out.println(i);
    stampadieci(i+1);
  }
}

Il metodo può accedere solo alle variabili locali e ai parametri.

Se gli occorre un dato, va passato come parametro.

Cicli indefiniti e ricorsione

Realizzo cicli indefiniti con la ricorsione

s=br.readLine();
while(s!=null) {
  System.out.println(s);
  s=br.readLine();
}

Lo posso fare in modo ricorsivo:

int leggiestampa(BufferedReader br)
  throws IOException {
  String s=br.readLine();
  if(s!=null) {
    System.out.println(s);
    leggiestampa(br);
  }
}

Notare:

• il metodo ha bisogno di br in tutte le chiamate; va quindi passato come parametro;
• il while della versione iterativa è diventato un if che contiene la chiamata ricorsiva.

Passaggio iterazione-ricorsione

Nei cicli e nella ricorsione, realizzo la ripetizione di istruzioni in modo diverso:

cicli

uso il costrutto while oppure for, che ripetono una certa istruzione finchè una condizione non diventa falsa

ricorsione

eseguo l'istruzione; se poi una condizione è vera ripeto; la ripetizione si realizza con una nuova invocazione ricorsiva

Istruzioni dopo la chiamata ricorsiva

Dopo la chiamata ricorsiva posso mettere altre istruzioni.

Esercizio

Cosa succede quando eseguo ricorsivo(3)?

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
      ricorsivo(i+1);
    System.out.println(i);
  }

Fare "come se fossero metodi diversi"

Riportare accanto al record di attivazione il punto del codice che si sta eseguendo

Rappresentazione grafica

Accanto al record di attivazione, scrivo il codice del metodo

Con una freccia, indico l'istruzione che sto eseguendo

i=3;

  static void ricorsivo(int i) {
--> System.out.println(i);
    if(i<5)
      ricorsivo1(i+1);
    System.out.println(i);
  }

Prima invocazione

i=3;

  static void ricorsivo(int i) {
--> System.out.println(i);
    if(i<5)
      ricorsivo1(i+1);
    System.out.println(i);
  }

Si stampa 3

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
--> if(i<5)
      ricorsivo1(i+1);
    System.out.println(i);
  }

i ha valore minore di 5: si fa la chiamata ricorsiva passando il valore di i+1, ossia 4

Seconda invocazione

Si crea un nuovo record di attivazione.

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
--> System.out.println(i);
    if(i<5)
      ricorsivo2(i+1);
    System.out.println(i);
  }

Attenzione: la esecuzione di ricorsivo è stata sospesa per eseguire ricorsivo1, ma non è terminata: quando ricorsivo1 termina, si riprenderà da dove si è lasciato.

Si stampa i

La i che viene stampata è quella del record di attivazione corrente, quindi si stampa 4.

Esecuzione del condizionale

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
--> if(i<5)
      ricorsivo2(i+1);
    System.out.println(i);
  }

Dato che i vale meno di 5, si invoca di nuovo il metodo.

Si passa il valore di i+1.

La i è quella dell'ultimo record, quindi i+1 vale 5.

Terza chiamata

Si crea un terzo record di attivazione

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
    if(i<5)
-->   ricorsivo2(i+1);
    System.out.println(i);
  }

i=5;

  static void ricorsivo2(int i) {
--> System.out.println(i);
    if(i<5)
      ricorsivo3(i+1);
    System.out.println(i);
  }

Si stampa il valore di i.

La i da guardare è l'ultima, e vale 5.

Esecuzione del condizionale

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
    if(i<5)
-->   ricorsivo2(i+1);
    System.out.println(i);
  }

i=5;

  static void ricorsivo2(int i) {
    System.out.println(i);
--> if(i<5)
      ricorsivo3(i+1);
    System.out.println(i);
  }

Questa volta i non è minore di 5, per cui non si fa la chiamata ricorsiva.

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
    if(i<5)
-->   ricorsivo2(i+1);
    System.out.println(i);
  }

i=5;

  static void ricorsivo2(int i) {
    System.out.println(i);
    if(i<5)
      ricorsivo3(i+1);
--> System.out.println(i);
  }

Si stampa ancora i, che è sempre 5.

Fine della terza invocazione

La terza invocazione termina, per cui si ammazza l'ultimo record di attivazione.

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
    if(i<5)
-->   ricorsivo2(i+1);
    System.out.println(i);
  }

Ero rimasto alla chiamata ricorsiva di ricorsivo2

Secondo le regole, devo semplicemente eseguire l'istruzione successiva.

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

i=4;

  static void ricorsivo1(int i) {
    System.out.println(i);
    if(i<5)
      ricorsivo2(i+1);
--> System.out.println(i);
  }

Viene stampato il valore di i, che ora è 4.

Attenzione! Nella chiamata ricorsivo2 la i valeva 5, ma in questa è sempre stato 4!

Come dire: la i di ricorsivo2 valeva 5 ma la i di ricorsivo1 è sempre stata 4.

Terminazione seconda invocazione

Il secondo record di attivazione viene distrutto, e si ritorna a ricorsivo:

i=3;

  static void ricorsivo(int i) {
    System.out.println(i);
    if(i<5)
-->  ricorsivo1(i+1);
    System.out.println(i);
  }

Riprendo da dove avevo lasciato: quindi eseguo la stampa.

Si stampa il valore di i, che questa volta è 3.

Alla fine si elimina anche questo record di attivazione.

Conclusione

Sono stati stampati:

3
4
5
5
4
3

Regola "a occhio":

• le istruzioni prima della invocazione ricorsiva vengono eseguite "in ordine" (prima quella della prima chiamata, poi quella della seconda, ecc)
• le istruzioni dopo la invocazione vengono eseguite in ordine inverso (la prima ad essere eseguita è la istruzione che sta nell'ultima chiamata ricorsiva)

Esercizio

Stampare le linee di un file in ordine inverso, senza usare i vettori e i cicli.

Soluzione

La lettura va fatta in ordine, per cui la faccio prima della chiamata ricorsiva.

La stampa va fatta in ordine inverso, per cui la faccio dopo.

  static void stampaInverso(BufferedReader br)
  throws IOException {
    String s=br.readLine();
    if(s!=null) {
      stampaInverso(br);
      System.out.println(s);
    }
  }

Principio: invece di usare il vettore, sfrutto il fatto di avere una variabile s diversa per ognuna delle chiamate ricorsive.

Progettazione metodi ricorsivi

Ci sono due modi:

• il modo sbagliato
• il modo giusto

Progettazione metodi ricorsivi

Come si progettano:

sbagliato:

pensare alla ricorsione come a un modo di realizzare cicli

sbagliato:

cercare di scrivere il metodo sulla base di come devono essere fatti i record di attivazione

giusto:

assunzione ricorsiva+verifica di terminazione

La simulazione dei record di attivazione va fatta solo alla fine per verificare se funziona.

Assunzione ricorsiva

I metodi ricorsivi si progettano facendo la seguente assunzione:

all'interno di un metodo, una invocazione ricorsiva produce il risultato corretto se viene fatta su un problema più semplice di quello di partenza

Il metodo di stampa inversa di un file

static void stampaInverso(BufferedReader br)
throws IOException {
  ...
}

Dentro posso fare una chiamata ricorsiva.

All'interno di un metodo, una invocazione ricorsiva produce il risultato corretto se viene fatta su un problema più semplice di quello di partenza

Applicazione del principio: dopo aver fatto String s=br.readLine(), la parte di file che resta da leggere contiene una linea di meno

Quindi, il problema della stampa in ordine inverso è stato semplificato

Quindi, l'invocazione stampaInverso(br) funziona correttamente

Quindi, viene stampato il resto del file in ordine inverso

Dato che poi stampo la prima linea, ottengo tutto il file stampato al contrario

Come un metodo predefinito

Una volta che il problema è stato semplificato, l'invocazione ricorsiva è corretta

È come se si trattasse di un metodo predefinito, come Math.sqrt, System.println, ecc.

Però questo metodo si può invocare soltanto dopo che il problema è stato semplificato

Esempio di progettazione

Devo scrivere questo metodo:

static void stampaInverso(BufferedReader br)
throws IOException {
  ...
}

Procedo in questo modo:

• assumo che esista un metodo predefinito System.inverseReadAndPrint(BufferedReader br)
• scrivo delle istruzioni per semplificare il problema
• quando il problema è stato semplificato, invoco il metodo predefinito
• al posto del metodo predefinito, ci metto la invocazione ricorsiva

Progettazione 1

static void stampaInverso(BufferedReader br)
throws IOException {
  ...
}

Per prima cosa, leggo una linea

È l'unica cosa che posso fare

static void stampaInverso(BufferedReader br)
throws IOException {
  String s=br.readLine();
  ...
}

Il problema è stato semplificato!

Ora br indica un file da leggere in cui una linea è stata già letta

Il problema è stato semplificato

Posso invocare il metodo ``predefinito'':

static void stampaInverso(BufferedReader br) throws
IOException {
	// legge prima linea
  String s=br.readLine();
	// stampa il resto del file al contrario
  System.inverseReadAndPrint(br);
}

Fine del metodo

Ho letto una linea, e stampato il resto del file al contrario; cosa manca?

Devo stampare la prima linea:

tatic void stampaInverso(BufferedReader br) throws
IOException {
	// legge prima linea
  String s=br.readLine();
	// stampa il resto del file al contrario
  System.inverseReadAndPrint(br);
	// stampa la prima linea
  System.out.println(s);
}

Applicazione dell'assunzione

Applicazione dell'assunzione: al posto del metodo predefinito (che non esiste) posso mettere la invocazione ricorsiva

static void stampaInverso(BufferedReader br) throws
IOException {
        // legge prima linea
  String s=br.readLine();
        // stampa il resto del file al contrario
  stampaInverso(br);
        // stampa la prima linea
  System.out.println(s);
}

Costruzione del metodo ricorsivo: riassunto

L'assunzione: dopo aver letto una linea, il problema è più semplice; quindi, stampaInverso(br) stampa in ordine inverso il resto del file

Algoritmo:

• leggo una linea
• stampa il resto del file al contrario
• stampa la prima linea

Il punto due si può realizzare con una invocazione ricorsiva

Costruzione: verifica di terminazione

A un certo punto, il metodo deve terminare.

Nel nostro caso, se s è null, non devo fare la chiamata ricorsiva, e nemmeno la stampa.

static void stampaInverso(BufferedReader br) throws IOException {
  String s=br.readLine();

  if(s!=null) {
    stampaInverso(br);
    System.out.println(s);
  }
}

Esercizio: stringhe palindrome

Scrivere un metodo di programma ricorsivo che decide se una stringa è palindroma.

Una stringa è palindroma se il primo carattere è uguale all'ultimo, il secondo al penultimo, ecc.

static boolean pali(String);

Stringhe palindrome: soluzione

Seguendo l'assunzione ricorsiva:

static boolean pali(String a) {
  ...
  pali(...);
  ...
}

La chiamata ricorsiva su una sottostringa di a è corretta.

Nota: pali(a) non è corretta, perchè il problema non è stato semplificato.

Prima stampaInverso(br) era corretta perchè dal file era stata letta una linea

Se prima br era un file in cui mancavano 10 linee da leggere, quando si fa l'invocazione ricorsiva è un file in cui ci sono solo 9 linee prima della fine del file

Non è il nome della variabile quello che conta, ma il fatto che rappresenti un problema più semplice

Stringhe palindrome: soluzione

Secondo l'assunzione ricorsiva, tutte queste invocazioni sono corrette:

pali(substring(1, a.length())

(invocazione sulla stringa tranne il primo carattere)

pali(substring(0, a.length()-1)

(invocazione sulla stringa tranne l'ultimo carattere)

pali(substring(1, a.length()-1)

(invocazione sulla stringa tranne il primo e l'ultimo carattere)

Tutte e tre le invocazioni sono corrette.

Quale invocazione ricorsiva usare?

L'invocazione pali(substring(1, a.length()-1) mi dice se la parte centrale della stringa è palindroma

Se lo è, basta poi vedere se il primo carattere è uguale all'ultimo.

• se la parte centrale della stringa non è palindroma, ritorna false
• altrimenti, verifica se il primo carattere è uguale all'ultimo

Stringhe palindrome: soluzione

Se la parte centrale della stringa non è palindroma, non lo è neanche la stringa intera.

  public static boolean pali(String a) {
    ...
    if(!pali(a.substring(1, a.length()-1)))
      return false;
    ...
  }

Stringhe palindrome: soluzione

Se la parte centrale è palindroma, allora devo controllare se il primo carattere è uguale all'ultimo:

  public static boolean pali(String a) {
    if(!pali(a.substring(1, a.length()-1)))
      return false;

    if(a.charAt(0)!=a.charAt(a.length()-1))
      return false;

    return true;
  }

Stringhe palindrome: soluzione

Manca il caso base

Se la stringa iniziale ha lunghezza dispari, arrivo alla chiamata con una stringa lunga 1.

Se inizio con una stringa di lunghezza pari, arrivo a una chiamata con la stringa vuota.

Ho due casi base!

  public static boolean pali(String a) {
    if(a.length()<=1)
      return true;

    if(!pali(a.substring(1, a.length()-1)))
      return false;

    if(a.charAt(0)!=a.charAt(a.length()-1))
      return false;

    return true;
  }

Perchè si ritorna true?

Quando la stringa ha un solo elemento, è chiaro che è palindroma.

Perchè la stringa vuota è palindroma?

Arrivo a fare la chiamata soltanto se ho una stringa con due caratteri uguali.

Palindrome: interpretazione matematica

Una stringa è palindroma se:

• il primo carattere è uguale all'ultimo
• la stringa fatta di tutti i caratteri meno il primo e l'ultimo è palidroma

Manca il passo base: una stringa di 0 oppure 1 carattere è palindroma.

Definizione basata sul principio di induzione.

Il metodo ricorsivo viene scritto seguendo letteralmente la definizione ricorsiva.

Progettazione metodi ricorsivi: riepilogo

• si scrive lo scheletro del metodo
• si sceglie un problema dello stesso tipo di quello di partenza, ma più semplice (anche se di poco)
• si assume che l'invocazione ricorsiva sia corretta (che funzioni correttamente) sul problema semplificato
• si mette l'invocazione ricorsiva nel corpo del metodo
• si scrive il resto del metodo: posso usare il risultato dell'invocazione ricorsiva
• si verifica che il metodo termini, ossia:
  1. non sto facendo l'invocazione sempre sugli stessi dati (es, non leggo da file prima della chiamata ricorsiva): prima della chiamata ricorsiva devo semplificare il problema
  2. ho una condizione che fa terminare le chiamate ricorsive
• a questo punto, si può verificare con i record di attivazione se il metodo funziona.

Il modo sbagliato è quello di partire dai record di attivazione e costruire il metodo in base a questi.

Ancora peggio: quando ho la chiamata ricorsiva, si ``ripete dall'inizio del metodo''

Questo causa la ``ripetizione dall'inizio'' dell'esame

Progettazione ricorsiva

All'inizio, può sembrare difficile

Una volta che si è capito dove si può mettere una invocazione ricorsiva è facile

Basta pensare che l'invocazione ricorsiva è corretta, senza pensare a cosa ``succede lí dentro''

Esercizio: il fattoriale

Scrivere una funzione che calcola il fattoriale di un numero in modo ricorsivo.

Condizione: il metodo non deve contenere for oppure while

Fattoriale: soluzione

Si inizia con la scrittura dello scheletro: serve un intero, e il valore di ritorno è un intero:

  public static int fattoriale(int i) {
    ...
  }

Fattoriale: chiamata ricorsiva

Invocare il metodo su i non funziona (il problema non è stato semplificato)

Invocare fattoriale(1) oppure fattoriale(i/2) funziona (sono problemi più semplici) però non servono

fattoriale(i-1) funziona (il problema è più semplice) e forse è utile

  public static int fattoriale(int i) {
    int j;

    ...

    j=fattoriale(i-1);

    ...
  }

Fattoriale: valore di ritorno

Il valore di ritorno di fattoriale(i-1) è corretto (assunzione ricorsiva).

Quindi vale:

1*2*3*...*(i-1)

Il fattoriale di i, che è quello che serve, vale:

1*2*3*...*(i-1)*i

Quindi, il fattoriale di i si ottiene calcolando fattoriale(i-1) e poi moltiplicando per i.

  public static int fattoriale(int i) {
    int j;

    j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: terminazione

Questo metodo ricorsivo non termina, perchè ogni volta che invoco il metodo questo invoca se stesso. Sempre.

Passo base della ricorsione: si deve prima o poi arrivare a un caso in cui non c'è la invocazione ricorsiva.

Nel caso del fattoriale: quando arrivo a i=0 posso direttamente dire che il fattoriale vale 1.

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

    j=fattoriale(i-1);
    return j*i;
  }

Definizione ricorsiva

La progettazione si può fare anche a partire dalla definizione ricorsiva del problema

La definizione di fattoriale si può anche dare come:

• il fattoriale di 0 è 1
• il fattoriale di i è dato dal fattoriale di i-1 moltiplicato per i

L'algoritmo ricorsivo implementa questa definizione

Il fattoriale di i-1 si calcola con la invocazione ricorsiva

Principio di induzione

La ricorsione funziona grazie al principio di induzione

Principio di induzione: se

• un enunciato è vero per n=0
• se l'enunciato è vero per n-1 allora è vero anche per n

Allora l'enunciato è vero per ogni n

Induzione e ricorsione

Parallelo:

Nel principio di induzione, quando faccio l'assunzione, non devo dimostrare che è vera

Assumo che sia vera

Quando scrivo metodi ricorsivi, non devo vedere cosa succede quando si fa la invocazione ricorsiva

Assumo semplicemente che sia corretta

Fattoriale: verifica a posteriori

Dopo aver terminato la progettazione posso verificare con i record di attivazione se è tutto a posto.

Va fatta particolare attenzione a:

• prima della chiamata ricorsiva il problema va semplificato, anche se di poco; altrimenti il metodo non termina
• esiste un caso in cui non viene fatta la invocazione ricorsiva (passo base)
• questo caso viene raggiunto comunque, prima o poi, indipendentemente dal valore iniziale

In questo caso: se i è negativo il passo base non viene mai raggiunto.

Il metodo va corretto, se lo si vuole invocare anche passando valori negativi.

Fattoriale: verifica con i record di attivazione

Esempio: fattoriale(3).

Prima invocazione:

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: seconda invocazione

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=2
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: terza invocazione

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=2
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=1
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: quarta invocazione

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=2
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=1
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=0
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
-->   return 1;

      j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: ritorno dalla quarta invocazione

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=2
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=1
j=1

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: ritorno dalla terza invocazione

i=3
j=indef

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

i=2
j=1

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Fattoriale: ritorno dalla seconda invocazione

i=3
j=2

  public static int fattoriale(int i) {
    int j;

    if(i==0)
      return 1;

--> j=fattoriale(i-1);
    return j*i;
  }

Si ritorna 2*3, ossia 6.

Palindrome: interpretazione matematica

Il problema delle stringhe palindrome si può risolvere in modo ricorsivo, esprimendo il problema in modo diverso

Una stringa è palindroma se:

• il primo carattere è uguale all'ultimo
• la stringa fatta di tutti i caratteri meno il primo e l'ultimo è palidroma

Manca il passo base: una stringa di 0 oppure 1 carattere è palindroma.

Definizione basata sul principio di induzione.

Il metodo ricorsivo viene scritto seguendo letteralmente la definizione ricorsiva.

  public static boolean pali(String a) {
    if(a.length()<=1)
      return true;

    if(a.charAt(0)==a.charAt(a.length()-1))
      if(pali(a.substring(1, a.length()-1)))
        return true;

    return false;
  }

Stringhe palindrome: il principio di induzione

Il programma funziona in base al principio di induzione:

passo base

il metodo è corretto per tutte le stringhe di lunghezza minore o uguale a uno;

assunzione induttiva

il metodo si assume che funzioni correttamente per stringhe di lunghezza minore o uguale a n-1

tesi induttiva

dato che si invoca pali(a.substring(1, a.length()-1)), in base alla assunzione induttiva questo metodo ritorna il risultato giusto; il metodo è stato scritto in modo che, se questo è vero, allora funziona

conclusione

il metodo è corretto per tutte le stringhe

Differenza induzione-ricorsione

• in matematica, la conclusione è data, e si sta solo cercando di dimostrarla
• in programmazione, la conclusione è che il programma è corretto, ma il programma lo sto ancora scrivendo

Si tratta di scrivere il programma in modo tale che la ``dimostrazione di correttezza'' funzioni

Scrivo il metodo seguendo la linea che userò per dimostrare che è corretto, ossia il principio di induzione

Semplificare il problema

Come si fa a dire che il problema è stato semplificato?

Un modo possibile è quello di contare le istruzioni che servono per risolverlo:

Il problema è semplificato se richiede meno operazioni

Esempi di semplificazione

Nei problemi visti finora:

Non sempre la semplificazione avviene attraverso la riduzione della dimensione dei dati

A volte è un cambiamento dei valori (es. diminzione di uno, nel caso del fattoriale) a semplificare il problema

Perchè funziona?

Sia n il numero di operazioni da fare

Scrivo il metodo in modo tale che sia corretto quando servono n operazioni

In questa fase, posso assumere che la invocazione ricorsiva sia corretta quando viene fatta su un problema per il quale bastano n-1 operazioni

Posso applicare il principio di induzione matematica, che dimostra che il metodo è corretto per qualsiasi numero di operazioni n

Manca solo il caso base (correttezza quando basta una sola operazione)

Esercizio

Scrivere un metodo ricorsivo che verifica se tutti i caratteri di una stringa sono uguali

Non si può usare for e nemmeno while

Scheletro

  public static boolean uguali(String s) {
    ...
  }

Assunzione: se faccio uguali(t), dove t è una stringa più corta di s, questo mi dice se t ha tutti i caratteri uguali

Problema semplificato

Se faccio una qualsiasi di queste invocazioni, il risultato è corretto:

  uguali(s.substring(0, s.length()-1))
  uguali(s.substring(1, s.length()))
  uguali("")
  uguali(s.substring(1, s.length()-1))
  ...

La terza non serve a niente

Le altre sí

Vediamo un programma basato sulla seconda

Invocazione ricorsiva

L'invocazione uguali(s.substring(1, s.length()) è corretta:

  public static boolean uguali(String s) {
    ...

    uguali(s.substring(1, s.length()))

    ...
  }

Mi dice se i caratteri dopo il primo sono tutti uguali

Come si usa?

Se i caratteri sono diversi, ritorno subito false:

  public static boolean uguali(String s) {

    if(!uguali(s.substring(1, s.length())))
      return false;

  }

Cosa manca?

Devo verificare se il primo carattere è uguale agli altri

Ma già so che gli altri sono uguali: basta fare il confronto con il secondo

  public static boolean uguali(String s) {

    if(!uguali(s.substring(1, s.length())))
      return false;

    if(s.charAt(0)!=s.charAt(1))
      return false;

    return true;
  }

Caso base

Se invoco il metodo su una stringa vuota, oppure fatta di un solo carattere, s.charAt(1) dà errore

In questi casi, so che la stringa è composta da caratteri uguali:

  public static boolean uguali(String s) {
    if(s.length()<=1)
      return true;

    if(!uguali(s.substring(1, s.length())))
      return false;

    if(s.charAt(0) != s.charAt(1))
      return false;

    return true;
  }

Ricorsione e array

Esercizio: decidere se un array di interi contiene un elemento, versione ricorsiva.

Contenimento

Inizio dallo scheletro del metodo

  public static boolean
  contiene(int v[], int e) {
    ...
  }

Come faccio la chiamata ricorsiva?

contiene(v, e) non si può fare: non ho semplificato il problema; continuo nell'invocazione all'infinito.

Ricerca nel vettore

Algoritmo: se l'elemento è il primo, ritorno true. Altrimenti, cerco nel resto del vettore.

  public static boolean
  contiene(int v[], int e) {

    if(v[0]==e)
      return true;

    // cerca nel resto del vettore
  }

Invocazione ricorsiva

Voglio cercare l'elemento nel resto del vettore

Creo un nuovo vettore che è uguale a v ma non contiene il primo elemento.

Creo un vettore di v.length-1 elementi.

Ci metto dentro i valori di v dal secondo all'ultimo:

public static boolean
contiene(int v[], int e) {

  if(v[0]==e)
    return true;

  int p[];
  p=new int[v.length-1];

  System.arraycopy(v, 1, p, 0, v.length-1);

  return contiene(p, e);
}

Se il resto del vettore contiene e si ritorna true, altrimenti false

Numero di operazioni

Per cercare un elemento in un array, quante operazioni servono?

Caso peggiore: un confronto per ogni elemento dell'array

Se la invocazione ricorsiva viene fatta su un array che ha un elemento di meno, il problema è stato semplificato
(infatti, questo problema si risolve con una istruzione di meno)

Si può fare la assunzione ricorsiva:
l'invocazione ricorsiva è corretta

Caso base

A ogni chiamata il vettore diventa più corto di uno.

Alla fine ho il vettore vuoto.

Il vettore vuoto non contiene la stringa da cercare

public static boolean
contiene(int v[], int e) {
  if(v.length==0)
    return false;

  if(v[0]==e)
    return true;

  int p[]=new int[v.length-1];
  System.arraycopy(v, 1, p, 0, v.length-1);
  return contiene(p, e);
}

Verifica: mancava un return false da qualche parte...

Evitare la copia

Copiare (quasi) l'intero vettore non è efficiente

Infatti, gli elementi vengono copiati uno per uno

Viene fatto un ciclo (dentro il metodo arraycopy)

Alternativa: passo lo stesso vettore, ma poi dico che la ricerca va fatta solo dal secondo elemento in poi

Ricerca in una parte del vettore: problema

Devo continuare la ricerca nella parte restante dell'array

  public static boolean
  contiene(int v[], int e) {

    ...

	// cerca in tutto il vettore
    return contiene(v, e);
  }

Come faccio a dire che voglio fare la ricerca solo in una parte del vettore?

contiene ha solo due argomenti, non posso speficiare il punto da cui iniziare la ricerca

Ricerca in una parte del vettore: soluzione

Specifico il punto in cui inizia la ricerca

Dato che l'invocazione sarà contiene(v, indice_inizio, e), il metodo deve avere un argomento in più

Metto un nuovo argomento nella funzione: il punto da cui iniziare la ricerca.

  public static boolean
  contiene(int v[], int start, int e) {
    ...
    return contiene(v, start+1, e);
  }

Invocazione-intestazione

Se un metodo va invocato con tre argomenti, deve avere tre parametri formali

Vale anche per i metodi ricorsivi

Soltanto che ora l'invocazione va fatta dentro il metodo stesso

public static boolean
contiene(int v[], int start, int e) {
    ...

    return contiene(v, start+1, e);
  }

Cosa fa il metodo?

Il metodo è più generale di quello di prima

Infatti, ora cerca un elemento a partire da un indice dato

Quando si scrive il metodo, bisogna tenere conto del fatto che il primo elemento da considerare è quello di indice start

Scrittura del metodo

Il metodo fa la ricerca a partire dall'indice start

1. il primo elemento da considerare è v[start]
2. quando ho start==v.length non ho più elementi da considerare (la parte di vettore da guardare è vuota)

Notare che, se start==v.length-1, allora c'è un elemento da considerare (l'ultimo elemento dell'array)

public static boolean
contiene(int v[], int start, int e) {
  if(start==v.length)
    return false;

  if(v[start]==e)
    return true;

  return contiene(v, start+1, e);
}

Ricorsione sui vettori, in generale

Il problema va semplificato

Di solito, questo avviene passando una parte del vettore nell'invocazione ricorsiva

Invece di creare un nuovo vettore, passo il vettore intero,
ma specifico in più quale parte del vettore va usata.

Questo modifica il prototipo del metodo!
(argomenti in più)

Vettori palindromi

Scrivere un metodo che verifica se il primo elemento del vettore è uguale all'ultimo, il secondo è uguale al penultimo, ecc.

Farlo su un vettore di stringhe

Vettori palindromi: algoritmo

• se il vettore ha zero oppure un elemento, allora è palindromo.
• se il primo non è uguale all'ultimo, ritorna false
• altrimenti, verifica se il vettore senza il primo e l'ultimo è palindromo.

Vettori palindromi: eliminare primo e ultimo

Due soluzioni:

• creo un nuovo vettore
• specifico il punto iniziale e quello finale della ricerca

Questa volta, non basta un indice solo per dire quale è la parte di vettore da considerare

Specifico punto iniziale e finale della ricerca

Il metodo ha due parametri in più: l'indice da cui iniziare la ricerca e quello a cui finire

  static boolean vettpal(String v[],
  int inizio, int fine) {
    ...
  }

Assunzione ricorsiva

L'invocazione ricorsiva è corretta, se viene fatta su una parte di vettore più piccola

Verifica: il numero di operazioni è proporzionale al numero di elementi da considerare

Operazione che mi serve: verificare se la parte centrale sia palindroma

Uso l'assunzione ricorsiva

La parte di vettore da guardare è quella che va da inizio a fine

Per fare la verifica sulla parte centrale, devo aumentare inizio e diminuire fine

  static boolean vettpal(String v[],
  int inizio, int fine) {
    ...
        vettpal(v, inizio+1, fine-1);
  }

Progetto il resto del metodo

Prima verifico se v[inizio] è uguale a v[fine]

  static boolean vettpal(String v[],
  int inizio, int fine) {

    if(!v[inizio].equals(v[fine]))
      return false;

    return vettpal(v, inizio+1, fine-1);
  }

Se sono diversi, allora so che la parte di vettore non è palindroma

Se sono uguali, faccio la verifica sulla parte centrale (tutto meno l'elemento iniziale e finale)

Caso base

Quando inizio==fine allora la parte di array da guardare ha un solo elemento (ossia v[inizio], che poi è lo stesso che v[fine]

  static boolean vettpal(String v[],
  int inizio, int fine) {
    if(inizio==fine)
      return true;

    if(!v[inizio].equals(v[fine]))
      return false;

    return vettpal(v, inizio+1, fine-1);
  }

Non basta!

Perchè?

Verifica a posteriori

Dopo aver scritto il metodo, si verifica la terminazione

Se l'array ha un numero dispari di elementi, ho la terminazione

Infatti, la sequenza di valori di inizio e fine dei record di attivazione è:

Alla fine, inizio==fine e si termina

Ma se l'array ha dimensione pari?

Array con numero pari di elementi

La sequenza dei valori di inizio e fine nei record di attivazione è:

Quando ora si invoca di nuovo il metodo, passo inizio+1 e fine-1

I parametri formali di questa invocazione sono:

Ora inizio vale più di fine

Secondo caso base

Quando inizio==fine, il vettore (la parte da guardare) ha solo un elemento

Quindi, il vettore di zero elementi si ottiene quando inizio==fine+1

Se l'array ha un numero di elementi pari, si arriva per forza a questa condizione (e non si arriva mai alla situazione inizio==fine)

Metodo completo

Il caso base è fatto di due casi: parte di vettore di uno oppure zero elementi

  static boolean vettpal(String v[],
  int inizio, int fine) {
    if(inizio>=fine)
      return true;

    if(!v[inizio].equals(v[fine]))
      return false;

    return vettpal(v, inizio+1, fine-1);
  }

La condizione inizio>=fine li comprende tutti e due

Variante con inizio e lunghezza

Può risultare più comoda da usare

Idea: invece di usare inizio e fine uso:

start

indice del primo elemento da guardare

quanti

numero di elementi da considerare

Per guardare tutto il vettore, valgono 0 e v.length

Algoritmo

Si usa sempre lo stesso algoritmo:

• se il vettore ha zero, oppure un elemento, allora è palindromo
• se il primo elemento è diverso dall'ultimo, allora non è palindromo
• altrimenti, verifica nella parte centrale

Progettazione ricorsiva

Modo alternativo per progettare il metodo:
scrivo l'intestazione e poi uso l'assunzione ricorsiva

  static boolean vettpal(String v[],
  int inizio, int quanti) {
    ...
  }

Qui dentro, l'invocazione di vettpal funziona (dà il risultato corretto), se gli passo un valore di quanti minore (parte di vettore composta da meno elementi)

Progettazione ricorsiva

Sulla base dell'assunzione ricorsiva, quando faccio vettpal(v, inizio+1, quanti-2), questo funziona

In questo modo, ho determinato se la parte centrale è palindroma

Cosa manca?

1. verificare se il primo è uguale all'ultimo
2. il caso base (vettore di uno o zero elementi)

Soluzione

Se il numero di elementi da guardare è zero oppure uno, si ritorna true

Se il primo non è uguale all'ultimo, si ritorna false

Altrimenti, si fa la verifica sulla parte centrale

static boolean vettpal(String v[],
int inizio, int quanti) {
  if(quanti<=1)
    return true;

  if(!v[inizio].equals(v[inizio+quanti-1]))
    return false;

  return vettpal(v, inizio+1, quanti-2);
}

Gli indici dei vettori

Ogni volta che faccio la chiamata ricorsiva, il primo indice aumenta di uno, ma il numero di elementi diminuisce di due

Perchè v[inizio+quanti-1] è l'ultimo elemento della parte da considerare?

Basta fare qualche prova: se quanti=1 deve venire v[inizio]; se quanti=2 deve venire v[inizio+1], ecc.

Trovare la posizione in una stringa

Esercizio: scrivere un metodo che prende come argomento una stringa e ritorna l'indice della prima posizione in cui appare la lettera 'a'

  static int prima(String s) {
    ...
  }

Assunzione ricorsiva

All'interno del metodo, la invocazione ricorsiva è corretta, se fatta su una stringa più corta

Quindi, prima(s.substring(1, s.length())) ritorna la prima posizione di 'a' nella stringa

Cosa ci faccio?

Come usare un risultato parziale

No:

s è la stringa a un certo punto della ricorsione, ossia potrebbe essere sia la stringa di partenza che una sottostringa a un certo punto della sequenza delle invocazioni ricorsive

Si:

s è la stringa ``di partenza'', ossia quella di cui voglio sapere la prima posizione di 'a'

Uso il risultato parziale

Se trovo 'a' in prima posizione, ritorno 0

Altrimenti, vado a vedere deve è nel resto della stringa

Cosa ci faccio con prima(s.substring(1, s.length()))?

Esempio:

s=                 "egfaswerfa"
s.substring(...)=   "gfaswerfa"

La posizione in s.substring(...) è 3

La posizione in s è 4

In generale: data la posizione nella sottostringa, quella nella stringa è +1

Il metodo completo

Se la stringa è vuota, ritorno 10000

Se il carattere sta in prima posizione, ritorno 0

Altrimenti, faccio la invocazione ricorsiva sulla sottostringa fatta di tutti i caratteri tranne il primo

static int prima(String s) {
  if(s.length()==0)
    return 10000;

  if(s.charAt(0)=='a')
    return 0;

  return prima(s.substring(1, s.length()))+1;
}

Espressione ricorsiva del problema

La posizione è:

• zero, se l'elemento sta in prima posizione
• la posizione nel resto della stringa più uno, altrimenti

Osservazione

Ho scritto il metodo pensando ad s come alla stringa iniziale

Non è la stringa ``a un certo punto''

Questo è corretto

Versione con valore di non presenza

Modificare il metodo in modo che torni -1 se la stringa non contiene 'a'

Dire perchè questo metodo non funziona:

static int prima(String s) {
  if(s.length()==0)
    return -1;

  if(s.charAt(0)=='a')
    return 0;

  return prima(s.substring(1,s.length()))+1;
}

Perchè non funziona?

verifica con record di attivazione:

quanto torno -1 dall'ultima invocazione (quando s=""), viene sommato 1

assunzione ricorsiva

se il valore di ritorno è -1, non devo ritornare questo valore più uno

Soluzione?

Soluzione

• se la stringa è vuota, ritorno -1
• se il carattere sta in prima posizione, ritorno 0
• guardo la posizione nel resto della stringa:
  • se è -1 (non c'è) ritorno -1
  • se il valore è maggiore o uguale a zero, ritorno questo valore più uno

Implementazione della soluzione

Dall'algoritmo al codice il passaggio è facile:

static int prima(String s) {
  if(s.length()==0)
    return -1;

  if(s.charAt(0)=='a')
    return 0;

  int r=prima(s.substring(1,s.length()));
  if(r==-1)
    return -1;
  else
    return r+1;
}

Memorizzo il valore di ritorno in una variabile, per evitare di dover invocare due volte il metodo

Suggerimento

Per i metodi ricorsivi:

mettere sempre il valore di ritorno in una variabile, e poi usarlo

Rende più difficile fare un errore tipico di quando si progettano metodi ricorsivi

Somma degli elementi di un vettore

Dato un vettore di interi, trovare il valore della somma

Realizzare un metodo ricorsivo

Definizione ricorsiva del problema

Si può definire la somma in questo modo:

• se il vettore è vuoto, la somma è zero
• altrimenti, la somma è data dalla somma di tutti gli elementi tranne l'ultimo, più l'ultimo

L'idea è che ``la somma di tutti tranne l'ultimo'' si può trovare con una invocazione ricorsiva

• se il vettore è vuoto, la somma è zero
• altrimenti, calcola la somma di tutti gli elementi tranne l'ultimo
• a questo valore, somma l'ultimo elemento, e ritorna

Progettazione ricorsiva

Modo alternativo:

• si assume che la invocazione ricorsiva sia corretta su un vettore più piccolo
• si scrive il resto del metodo, usando questa assunzione

I parametri

Esistono vari modi per specificare una parte di un vettore

Questa volta: passiamo il numero di elementi da considerare

  static int somma(int v[], int quanti) {
    ...
  }

Questo metodo calcola la somma dei primi quanti elementi del vettore v

Osservazione

Il metodo che realizzo è più generale di quello richiesto

Infatti, calcola la somma dei primi quanti elementi, non di tutti

Ma...

anche se quanti è diverso da v.length, questo non vuol dire che sono in una invocazione ricorsiva ``in mezzo''

Si deve sempre pensare che:

• il metodo può venire invocato anche su una parte del vettore
• i valori di v e quanti sono quelli iniziali, non quelli ``a un certo punto''
• devo calcolare la funzione ``estesa'', cioè quella che trova la somma di una parte qualsiasi del vettore

Assunzione ricorsiva

L'invocazione somma(v, quanti-1) dà la somma:

v[0]+...v[quanti-2]

È la somma dei primi quanti-1 elementi

Per trovare la somma dei primi quanti cosa manca?

La somma dei primi quanti è:

v[0]+...v[quanti-2]+v[quanti-1]

Devo sommare il valore di v[quanti-1]

Implementazione

Sommo tutti gli elementi da considerare tranne l'ultimo (invocazione ricorsiva)

Poi, sommo l'ultimo elemento da considerare

  static int somma(int v[], int quanti) {
    if(quanti==0)
      return 0;

    int parziale=somma(v, quanti-1);

    return parziale+v[quanti-1];
  }

Il caso base è quanti==0: se non ci sono elementi da considerare, la somma è zero

Modo sbagliato

Adesso vediamo un modo sbagliato di progettare i metodi ricorsivi

Se non capite perchè questo modo è sbagliato, non avete capito come funziona la ricorsione

Un metodo ricorsivo che non funziona

Questo errore viene fatto molto spesso da chi non ha capito la ricorsione:

Studente impreparato: dato che la chiamata ricorsiva fa ripartire il metodo dall'inizio, io sommo un elemento, incremento il valore di i, e poi faccio la chiamata ricorsiva:

  static int sommaErr(int v[], int i) {
    int somma;

    if(i>=v.length)
      return 0;

    somma=somma+v[i];

    sommaErr(v, i+1);

    return somma;
  }

Professore: torni la prossima volta

Dire perchè non funziona

Soluzione

Intanto, la variabile somma viene usata senza essere stata inizializzata:

    int somma;

    if(i>=v.length)
      return 0;

    somma=somma+v[i];

Anche mettendo int somma=0, non funziona lo stesso

Le variabili dei metodi ricorsivi

Quando si scrive una variabile in un metodo ricorsivo:

  int somma;

Questa non è una singola variabile!

Si crea una variabile per ogni invocazione del metodo

Cosa succede in pratica

Non è vero che la variabile somma ``accumula'' i valori del vettore

Infatti, ho più variabili di nome somma:
se ne crea una ogni volta che si invoca ricorsivamente il metodo

Come si interpreta un metodo ricorsivo

Regola generale (anche per metodi non ricorsivi):

Se so che il metodo funziona, quando lo invoco non mi interessa il modo in cui lavora (le operazioni che vengono fatte nel corpo)

Esempio: non mi interessa quali sono le istruzioni di Math.sqrt, mi basta sapere che il risultato è corretto

Ma sopratutto:

l'unica interazione fra un metodo e quello che lo ha invocato è attraverso i parametri e il valore di ritorno

Applicazione ai metodi ricorsivi

Quando scrivo una invocazione ricorsiva dentro un metodo:

  static int somma(...) {

    somma(...)

  }

È come se somma fosse un altro metodo, di cui non conosco l'implementazione

So soltanto che, passando un vettore e un intero, lui calcola la somma e lo dà come valore di ritorno

Quello che è stato calcolato viene restituito: per usarlo devo fare variabile=somma(...) oppure usare somma(...) all'interno di una espressione

I parametri in più

Nei metodi ricorsivi su vettori, usiamo uno o due parametri in più (indice primo elemento da guardare, e poi indice ultimo oppure numero di elementi da guardare)

Esempio: per verificare se un vettore è palindromo:

  static boolean vettpal(String v[],
  int inizio, int quanti) {
    ...
  }

Se voglio guardare tutto il vettore, devo fare:

  vettpal(v, 0, v.length);

Metodo iniziale

Di solito, l'operazione va fatta su tutto un vettore

Per evitare di avere ogni volta i due parametri aggiuntivi nella invocazione, metto un metodo intermedio:

  static boolean vettorePalindromo(String v[]) {
    return vettpal(v, 0, v.lenght);
  }

Questo metodo si può invocare passando il solo vettore:

  if( vettorePalindromo(unArray) ) {
    ...
  }

Non è un metodo ricorsivo!

Serve solo per invocare il metodo ricorsivo con i valori dei due parametri inizio e fine che corrispondono a tutto l'array

Esercizio

Scrivere un metodo ricorsivo che: data una LinkedList e un oggetto, ritorna il numero di oggetti della lista che sono equals all'altro oggetto

U

Scheletro

Sarebbe cosí:

  static int quanteVolte(LinkedList l, Object o) {
    ...
  }

Però cosí non posso fare l'invocazione ricorsiva!

Copia/indici

Due soluzioni:

• creo una nuova lista, in cui metto tutti gli elementi della vecchia tranne uno
• uso indici per dire quale parte della lista guardare

Nel secondo caso, ho due possibilità:

• indice del primo elemento da guardare
• numero di elementi da guardare

Soluzione con numero di elementi

Scheletro:

static int quanteVolte(LinkedList l, int quanti, Object o) {
  ...
}

quanti indica quanti elementi della lista devo guardare

Gli elementi da guardare sono l.get(0)...l.get(quanti-1)

Assunzione ricorsiva

Il valore di quanteVolte(l, quanti-1, o) è corretto

Dice quanti elementi uguali a o ci sono nei primi quanti-1 elementi della lista

Cosa manca?

Calcolo delle occorrenze

static int quanteVolte(LinkedList l, int quanti, Object o) {

  int r=quanteVolte(l, quanti-1, o);

  ...
}

Ora so che r contiene il numero di occorrenze (quante volte) l'oggetto appare nella lista, negli indici 0...quanti-2

Cosa manca?

Se l'elemento in posizione quanti-1 è diverso da o, ritorno r

Se l'elemento in posizione quanti-1 è uguale ad o, restituisco r+1

Metodo completo

Il caso base è quando quanti==0
(si ritorna 0)

static int quanteVolte(LinkedList l,
  int quanti, Object o) {
  if(quanti==0)
    return 0;

  int r=quanteVolte(l, quanti-1, o);

  if(l.get(quanti-1).equals(o))
    return r+1;
  else
    return r;
}

Seconda soluzione

Faccio il conteggio su una parte della lista

Conto solo a partire da un certo indice in poi

static int quanteVolte(LinkedList l,
int primo, Object o) {
  ...
}

Caso base

Quando primo==l.size()-1 allora ho un solo elemento da considerare

Quando primo==l.size(), non ho nessun elemento da guardare

Modo alternativo di capire quale è il caso base:

Se faccio il conteggio su tutta la lista:
se la lista è vuota allora l.size() vale 0;
alla prima invocazione devo subito terminare
ma, alla prima invocazione, primo vale 0

Quindi, se primo==l.size() ho il caso base

Assunzione ricorsiva

Se faccio quanteVolte(l, primo+1, o) questo dà il risultato corretto

Cosa manca?

Se l'elemento sta anche in prima posizione, allora devo sommare uno a questo valore

static int quanteVolte(LinkedList l,
int primo, Object o) {

  if(primo==l.size())
    return 0;

  if(l.get(primo).equals(o))
    return quanteVolte(l, primo+1, o)+1;
  else
    return quanteVolte(l, primo+1, o);
}

Implementazione alternativa

Prima faccio la invocazione ricorsiva, e poi vedo se tornare il valore, oppure il valore aumentato di uno

static int quanteVolte(LinkedList l,
int primo, Object o) {
  if(primo==l.size())
    return 0;

  int r=quanteVolte(l, primo+1, o);

  if(l.get(primo).equals(o))
    return r+1;
  else
    return r;
}