Lezione di Mercoledi' 13/02/02 - ultimo aggiornamento: 25/02/02

Classificazione delle diverse forme di ricorsione (con esempi)

CHE COSA E' STATO FATTO A LEZIONE

Una classificazione delle diverse forme ricorsione

Per la definizione di "ricorsione mutua", "ricorsione diretta", "funzione ricorsiva non lineare", "funzione ricorsiva lineare", "chiamata ricorsiva di coda", "funzione ricorsiva di coda", consultare [NOTE1: pag 34-36].

Esempio di funzioni mutuamente ricorsive

/*
  AI: "n" >= 0
  AF: Resituisce 1 se "ne" e' pari, 0 altrimenti
*/
int pari (int n);

/*
  AI: "n" >= 0
  AF: Resituisce 1 se "ne" e' dispari, 0 altrimenti
*/
int dispari (int n);

int pari (int n)
{
  if (n==0) return 1
  else return dispari(n-1);
}

int dispari (int n)
{
  if (n==0) return 0
  else return pari(n-1);
}

Esempio di funzione ricorsiva non lineare

La funzione "Move" per risolvere il gioco delle "Torri di Hanoi" (che abbiamo visto la lezione scorsa).

/*
   AI: Ci sono almeno "count" dischi sulla torre "start".
       Il disco in cima a ciuscuna delle torri "temp" e "finish"
       (se presente) e' piu' largo di ciacuno dei "count" dischi
       in cima alla torre "start".
   AF: Sono state stampate su terminale le azioni necessarie per:
       spostare (rispettando le regole del gioco) i "count" dischi 
          dalla cima alla torre "start" 
          alla cima alla torre "finish"
       riportando la torre "temp" (usata come deposito ausiliario per
       i dischi) allo stato in cui si trovava al momento della chiamata.
*/

int Move (int count, int start, int finish, int temp)
{
    if (count > 0)
       {
          Move(count-1,start, temp, finish);
          printf("Muovi un disco da %d a %d.\n",start,finish);
          Move(count-1, temp, finish, start);
       }
}

Esempio di funzione ricorsiva lineare (ma NON ricorsiva di coda)

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

Esempio di funzione ricorsiva di coda

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma tutti gli elementi pari di a[first..last]
*/
int conta_pari (int[] a, int first, int last)
{
     return conta_pari_rt(a,first,last,0);
}
/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma 
      di "acc" e di tutti gli elementi pari di a[first..last]
*/
int conta_pari_rt (int[] a, int first, int last, int acc)
{
  if (first > last)
     return acc;
  else if ((a[first] % 2) == 0)
     return conta_pari_rt(a,first+1,last,acc+1);
  else 
     return conta_pari_rt(a,first+1,last,acc);
}

Esempio di funzione iterativa ottenuta eliminando la ricorsione di coda

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma tutti gli elementi pari di a[first..last]
*/
int conta_pari (int[] a, int first, int last)
{
    int acc = 0;

    while (first <= last)
    {
       if ((a[first] % 2) == 0)
          acc=acc+1;
      
       first=first+1;
    }
    
    return acc;
}

Altro esempio di funzione ricorsiva di coda

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: Restituisce la somma tutti gli elementi pari di a[first..last]
*/
int conta_pari2 (int[] a, int first, int last)
{
     int ris = 0;
     conta_pari_rt2 (a,first,last,&ris);
     return ris;
}
/*
  AI: "first" e "last" sono indici validi per "a"
  AF: *"acc" e' stato incrementato con la somma 
      di tutti gli elementi pari di a[first..last]
*/
void conta_pari_rt2 (int[] a, int first, int last, int *acc)
{
  if (first <= last)
     { 
        if ((a[first] % 2) == 0) *acc = *acc + 1;
        conta_pari_rt2(a,first+1,last,acc);
     }
}

Altro esempio di funzione iterativa ottenuta eliminando la ricorsione di coda

/*
  AI: "first" e "last" sono indici validi per "a"
  AF: *"acc" e' stato incrementato con
      la somma tutti gli elementi pari di a[first..last]
*/
void conta_pari (int[] a, int first, int last, int *acc)
{
    while (first <= last)
    {
       if ((a[first] % 2) == 0)
          *acc = *acc + 1;
      
       first=first+1;
    }

COSA SI DEVE LEGGERE

• [NOTE1: pag. 27-29]
• [NOTE1: pag. 34-36]

ESERCIZI DA SVOLGERE

• Simulare l'esecuzione delle funzioni sviluppate in precedenza.