2016 – 4

Si consideri il seguente programma:

#include 
int max(int a, int b)
{
   if(a > b) return a;
   return b;
}
int f(int a, int b) 
{
   if(a == b) return b;
   if(a <  0) return -b;
   return max(f(a-1,2*b), f(a-1,2*b+1));
}
int main() 
{
   printf("V = %d\n", f(10,0));
   return 0;
}

Qual è il numero intero V stampato a video dal programma?

Soluzione: V=7

La chiamata iniziale si espande...

f(10,0)

f(9,0), f(9,1)

f(8,0), f(8,1), f(8,2), f(8,3)

f(7,0), f(7,1), f(7,2), f(7,3), f(7,4), f(7,5), f(7,6), f(7,7)

f(6,0), f(6,1), f(6,2), f(6,3), f(6,4), f(6,5), f(6,6), f(6,7), f(6,8), f(6,9), f(6,10), f(6,11), f(6,12), f(6,13), 7

... 6 ... 7

7

Osserva

1. le chiamate con a=b restituiscono il valore b
2. f(7,7) è la chiamata più alta con a=b e restituisce il valore massimo 7
3. le chiamate successive continuano con valori di a sempre più bassi e restituiranno i valori 6, 5, 4, 3, 2, 1, 0
4. quando il valore di a diventerà negativo si otterrà il valore -b, quindi negativo.