Si consideri la seguente funzione:
int A(int n, int m) { if(n == 0) return 1; else if(n%2 == 0) return A(n/2,m)*A(n/2,m); else return m*A(n-1,m); }Dire quale sarà il valore tornato dalle chiamate
- A(3,2)
- A(4,3)
- A(5,4)
Soluzione: 8, 81, 1024.
Prova…
0 1 2 3 4 0 1 1 1 1 1 1 0 1 2 3 4 2 0 1 4 9 16 3 0 1 8 27 64 4 0 1 16 81 256 5 0 1 32 243 1024
Osserva
- n=0: 1
- n=1: m*A(0,m) = m*1 = m
- n=2: A(1,m)*A(1,m) = m*m = m2
- n=3: m*A(2,m) = m*m2 = m3
- n=4: A(2,m)*A(2,m) = m2*m2 = m4
- n=5: m*A(4,m) = m*m4 = m5
Quindi
A(n,m) = mn