risoluzione di un ciclo if (esame programmazione)

[ferra03]

Buon giorno a tutti,

Mi presnto sono ferra03 mi sono iscritto da poco a questo forum e volevo chiedervi un aiuto per un problema, devo sostenere un'esame di programmazione e c'è un'esercizio di un facsimile del mio esame che proprio non riesco a capire , vi copio il testo:

Scrivere nel riquadro il risultato ottenuto invocando il seguente
metodo ricorsivo con la chiamata f(5).

public static int f(int x) {
if (x == 0 || x == 1)
return x;
return f(x/2) + f(x%2) + x;
}

chiamando f(5) la soluzione pubblicata dal prof. è 9 e non riesco a capire il perchè, vi sarei grato se potese darmi una mano.

Grazie a tutti in anticipo

[andbin]

Originariamente inviato da ferra03
public static int f(int x) {
if (x == 0 || x == 1)
return x;
return f(x/2) + f(x%2) + x;
}

chiamando f(5) la soluzione pubblicata dal prof. è 9 e non riesco a capire il perchè

Essendo un metodo ricorsivo, basta che deduci il flusso e cosa viene passato e poi restituito dai livelli inferiori di ricorsione.

All'inizio viene invocato con 5. Dentro hai 2 invocazioni ricorsive: una con valore 2 e l'altra con valore 1. Ecc....

[ferra03]

Grazie andbin per la tua risposta, il problema è che io ho provato a fare come dici tu solo che comunque non riesco a risolverlo potresti scrivermi i passaggi?

[andbin]

Originariamente inviato da ferra03
Grazie andbin per la tua risposta, il problema è che io ho provato a fare come dici tu solo che comunque non riesco a risolverlo potresti scrivermi i passaggi?

f(5)
fa eseguire:
f(2) + f(1) + 5


f(2)
fa eseguire:
f(1) + f(0) + 2

Per via del test iniziale, f(1) e f(0) ritornano subito questo valore.

Quindi alla fine è equivalente alla somma di:

1 + 0 + 2 + 1 + 5

[mxa]

f(5) = f(2) + f (1) + 5
f(2) = f(1) + f(0) + 2
f(0) = 0
f(1) = 1

da questo deriva che:
f(2) = 1 + 0 + 2 = 3
e quindi:
f(5) = 3 + 1 + 5 = 9.

[ferra03]

grazie mille andbin ora ho capito