Programmazione per TWM: Esercitazione di laboratorio #11 (25/02)

L'obiettivo di questa esercitazione è la familiarizzazione con la ricorsione (capitolo 6).

Raccomandazioni: Ove non altrimenti indicato, rispondete alle domande prima ragionando su carta e poi provando a editare, compilare ed eseguire. Gli esercizi etichettati con l'asterisco (*) sono più difficili: affrontateli dopo aver risolto gli altri.

Esercizio 1

Obiettivo: Scrivere i primi metodi ricorsivi.

Attività:

1. Completate il seguente programma, scrivendo il metodo ricorsivo (e senza cicli!) per assegnare 1 a tutti gli elementi di un array unidimensionale.

   class UniRicorsivo {
     public static void main (String[] args) {
       int[] a = {0,0,0,0,0,0,0,0,0,0};
       assegnaUni(a,0);
       for (int i = 0; i < a.length; i++) 
         System.out.print(a[i] + " ");
       System.out.println();
     }
   
     static void assegnaUni(int[] v, int low) {
       //COMPLETARE QUI
     }
   }
   

2. Aggiungete al programma precedente un metodo assegnaUni(int[]) che assegna 1 a tutti gli elementi dell'array passato come parametro, richiamando il metodo assegnaUni(int[], int) con gli argomenti opportuni. Modificate anche il programma principale.
3. Aggiungete al programma precedente un metodo ricorsivo (e quindi senza cicli!) assegnaI(int[], int) per assegnare i a ogni elemento a[i] di un array unidimensionale (e quindi 0 ad a[0], 1 ad a[1], e così via...).
4. Aggiungete al programma precedente un metodo ricorsivo (e senza cicli!) per assegnare 1 a tutti gli elementi di un array bidimensionale. Suggerimento: Usate anche il metodo assegnaUni(int[]) definito prima...

Esercizio 2

Obiettivo: Scrivere altri metodi ricorsivi.

Attività:

1. Scrivete un metodo ricorsivo inputSOrN() per il controllo dell'input: il metodo deve leggere (usando EasyIn.readChar()) un carattere in input finché non viene letto 's' o 'S' o 'n' o 'N'. Sarà una funzione o una procedura?
2. Scrivete un metodo ricorsivo per calcolare la funzione di Ackermann, definita da:

      ackermann(0,n) = n+1
      ackermann(m,0) = ackermann(m-1,1)
      ackermann(m,n) = ackermann(m-1,ackermann(m,n-1))
   

   Questa funzione è interessante perché vi mostra un esempio di funzione ricorsiva con ricorsione annidata. Questo significa che la funzione di Ackermann cresce molto rapidamente. Si consideri ad esempio che la funzione f(x) = ackermann(x,x) cresce molto più rapidamente di qualsiasi polinomio o esponenziale. Già calcolando ackermann(4,1) si può avere stack overflow!
3. Scrivete un metodo ricorsivo static boolean tuttiZeri(int[] a, int i) per verificare se gli elementi di un array sono tutti nulli fino alla posizione i.
4. (*) Scrivete un metodo per verificare se una matrice quadrata passatagli come argomento è triangolare superiore, ossia se tutti i valori al di sotto della diagonale principale sono nulli. Il metodo deve essere una funzione con valore restituito boolean. Scrivetene una versione ricorsiva che usa il metodo tuttiZeri(int[], int) appena definito e (opzionale) una versione iterativa.

Esercizio 3

Obiettivo: Sull'utilità della ricorsione.

Attività:

1. Scrivete un programma per confrontare la velocità degli ordinamenti per selezione e per fusione. Provatelo con array di varie dimensioni (anche decine di migliaia di elementi). Usate il metodo Math.random() (che restituisce un double) per "riempire" l'array (ossia, per assegnargli dei valori).

Esercizio 4

Obiettivo: Scrivere ancora altri metodi ricorsivi.

Attività:

1. (*) Scrivete un metodo che verifica se una matrice quadrata passatagli come argomento è triangolare inferiore. Scrivetene una versione ricorsiva e (opzionale) una versione iterativa.
2. Scrivete un metodo che verifica se una matrice quadrata passatagli come argomento è triangolare. Usate i metodi definiti in precedenza: il corpo di questo metodo sarà di una riga.
3. Scrivete un metodo che verifica se una matrice quadrata passatagli come argomento è diagonale (tutti gli elementi che non stanno sulla diagonale principale sono nulli). Usate i metodi definiti in precedenza: il corpo di questo metodo sarà di una riga.
4. Riprendete l'esercizio 2.3: scrivete un metodo per determinare se un array ha valori nulli dall'indice i in poi (ricorsivo e iterativo). Nota: Questo metodo vi sarebbe stato utile per l'esercizio 4.1: non l'avevate definito? Male...
5. Generalizzate l'esercizio precedente : scrivete un metodo per determinare se un array ha i valori dall'indice i a j nulli (ricorsivo e iterativo).
6. (*) Scrivete un metodo che restituisce la trasposta di una matrice quadrata passatagli come argomento. Scrivetene sia una versione ricorsiva sia una versione iterativa.
7. (*) Scrivete un metodo ricorsivo per calcolare il determinante di una matrice quadrata.

Stefano Mizzaro Last modified: Sat Jul 10 11:31:54 ora legale Europa occidentale 2004