Corso di Fondamenti di Informatica A

Soluzione agli esercizi proposti in laboratorio

Esercitazione n. 4

Massimo

int max(int a, int b)
{
    return (a>b ? a : b);
}

int max3(int a, int b, int c)
{
    return max(max(a,b),c);
}

Calcolo della somma dei primi N numeri pari

int somma_pari(int N)
{
    if (N==0)
        {return 0; }
    else
        return 2*(N-1)+somma_pari(N-1);
}

La funzione scritta non è tail ricorsiva, infatti dopo la chiamata ricorsiva deve ancora essere effettuata la somma. Il compilatore non potrebbe quindi effettuare l'ottimizzazione tail, cioè riutilizzare il record di attivazione di una chiamata per eseguirne un'altra.
Per avere una versione tail ricorsiva è necessario inserire un nuovo parametro che rappresenta la somma calcolata fino a quel momento.

int somma_pari_tail(int N, S)
{
    if (N==0)
        {return S; }
    else
        return somma_pari_tail(N-1,S+2*(N-1));
}

Potenza di un numero

float potenza(float M, int N)
{   float P;
    if (N==0)
        { return 1; }
    else
        if (N%2 == 0) /* Se N è pari */
            { P = potenza(M,N/2);
              return P*P; }
        else
            { return potenza(M,N-1)*M; }
}

La funzione è ricorsiva, ma non tail ricorsiva, infatti dopo la chiamata ricorsiva devono ancora essere effettuati dei prodotti (sia nel caso di N pari sia in quello di N dispari).
È possibile scriverla in maniera tail ricorsiva, osservando che, nella funzione precedente, vengono calcolate tutte le potenze del tipo M^(2i), per tutti gli i tali che  2i<N ovvero M1, M2, M4, M8, ... Aggiungeremo quindi due parametri. P rappresenta la potenza calcolata fino a questo momento; P2 rappresenta la potenza M^(2i) accumulata fino a questo momento. Se N è pari, allora dovremo moltiplicare P per P2.

float potenza_tail(float M, int N, float P, float P2)
{
    if (N==0)
        { return P; }
    else
        if (N%2 == 0)
            { P2=P2*P2;
              return potenza_tail(M,N/2,P,P2);
            }
        else
            { P = P*P2;
              return potenza_tail(M,N-1,P,P2);
            }
}

float potenza_2(float M, int N)
{
    return potenza_tail(M,N,1,M);
}

Visto che è stato possibile scriverla in maniera tail ricorsiva, è evidentemente possibile scriverla anche in maniera iterativa. Infatti un compilatore che esegue l'ottimizzazione tail effettuera` il calcolo in maniera iterativa. In questo caso, dovremo essere noi a scrivere il ciclo corrispondente. Prendiamo una variabile i che ci servira` come indice e che fara` le veci del parametro N nella versione tail ricorsiva.

float potenza_non_ric(float M, int N)
{ float P, P2;
  int i;

  i = N;
  while (i>0)
   { if (i%2 == 0)
          { P2=P2*P2;
            i = i/2;
          }
      else
          { P = P*P2;
            i = i-1;
          }
   }
}

Il numero di prodotti effettuati risulta crescere approssimativamente come log2(N), infatti in entrambi i rami dell'if c'è un solo prodotto; il ciclo while viene ripetuto un numero di volte che varia fra log2(N) e 2log2(N).
Nota: La versione iterativa è molto meno intuitiva rispetto a quella ricorsiva.