Lezione di Lunedi' 11/02/02 - ultimo aggiornamento: 12/02/02

Ancora ricorsione.

CHE COSA E' STATO FATTO A LEZIONE

Funzioni ricorsive che stampano gli elementi di un array

Stampa ricorsiva di una porzione di un array di interi (questa funzione e' ricorsiva di coda, e la sua asserzione iniziale e' "piu' generale" di quella della funzione "printarr_rt" in [NOTE1: pag. 38]).)

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Stampa tutti gli elementi di a[first..last]
*/
void print_arr_rt (int[] a, int first, int last)
{
  if (first <= last)
  {
     printf("%d", a[first]);
     print_arr_rt(a,first+1,last);
  }
}

Stampa ricorsiva di una porzione di un array di interi in ordine inverso (questa funzione NON e' ricorsiva di coda, e la sua asserzione iniziale e' "piu' generale" di quella della funzione "printarr_rn" in [NOTE1: pag. 38]).)

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Stampa tutti gli elementi di a[first..last]
*/
void print_arr_inv_rn (int[] a, int first, int last)
{
  if (first <= last)
  {
     print_arr_inv_rn(a,first+1,last);
     printf("%d", a[first]);
  }
}

Stampa ricorsiva di una porzione di un array di interi in ordine inverso (ATTENZIONE: questa funzione e' una versione ricorsiva di coda della funzione precedente

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Stampa tutti gli elementi di a[first..last]
*/
void print_arr_inv_rt (int[] a, int first, int last)
{
  if (first <= last)
  {
     printf("%d", a[last-1]);
     print_arr_inv_rt(a,first,last-1);
  }
}

Funzioni ricorsive che effettuano "operazioni di aggregazione" sugli elementi di un array

Somma ricorsiva di una porzione di un array di interi (questa funzione NON e' ricorsiva di coda, e "generalizza" la funzione "sumarr_rn" in [NOTE1: pag. 38]).)

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma degli elementi di a[first..last]
*/
int sum_arr_rn (int[] a, int first, int last)
{
  if (first > last)
     return 0;
  else
     return a[first] + sum_arr_rn(a,first+1,last);
}

Versione ricorsiva di coda della funzione precedente. NOTA: per mantenere inalterato il prototipo (tipo del risultato e nome, numero, e tipo dei parametri) e' stato necessario "incapsulare" la funzione ricorsiva dentro un'altra funzione.

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma degli elementi di a[first..last]
*/
int sum_arr (int[] a, int first, int last)
{
   return sum_arr_rt(a,first,last,0);
}

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce il valore ottenuto sommando di "acc" e
      gli elementi di a[first..last]
*/
int sum_arr_rt (int[] a, int first, int last, int acc)
{
  if (first > last)
     return acc;
  else
     return sum_arr_rn(a,first+1,last, a[first]+acc);
}

Altra versione (sempre ricorsiva di coda) della funzione precedente. NOTA: anche in questo caso per mantenere inalterato il prototipo (tipo del risultato e nome, numero, e tipo dei parametri) e' stato necessario "incapsulare" la funzione ricorsiva dentro un'altra funzione.

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma degli elementi di a[first..last]
*/
int sum_arr1 (int[] a, int first, int last)
{
   int r = 0;
   sum_arr_rt(a,first,last,&r);
   return r;
}

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Il valore di partenza di "*ris" e'
      stato incrementato con la somma degli elementi di a[first..last]
*/
void sum_arr_rt (int[] a, int first, int last, int *ris)
{
  if (first<=last)
     {
      *ris+=a[first];
      sum_arr_rt(a,first+1,last,ris);
     }
}


Somma ricorsiva di una porzione di un array di interi
che resituisce la somma in un parametro 
passato per riferimento
(questa funzione  
"generalizza" la funzione 
"sumarr_rt" in [NOTE1: pag. 38])).
La funzione "sum_arr_rt" e quella sviluppata al punto precedente
/*
  AI: "first" e "last" sono indici validi per "a"
  AF: "*ris" contiene la somma degli elementi di a[first..last]
*/
void sum_arr2 (int[] a, int first, int last, int *ris)
{
   *ris = 0;
    sum_arr_rt(a,first+1,last,ris);
  
}




Funzione ricorsiva per risolvere il gioco delle "Torri di Hanoi"

Consultare il [KRUSE] (vedi sezione "COSA SI DEVE LEGGERE").


COSA SI DEVE LEGGERE



[NOTE1: pag. 37-38]

[KRUSE: pag.95-100] (ATTENZIONE: questa parte di testo e' fondamentale,
se ci sono problemi con l'"inglese tecnico"
usato nel libro, non esitate a rivolgervi al docente).



ESERCIZI DA SVOLGERE



Simulare l'esecuzione delle funzioni
sviluppate in precedenza.