[java]ricorsione

[xxx81xxx]

Scuate il disturbo,
mi potreste cortesemente aiutare a capire come funziona la ricorsione in questo caso?


Il mio problema e' che all'inizio la x e' = 7
quindi devo eseguire l'ultima istruzione

return 3 * f(n / 2) + 4 * f(n % 2);

--> io faccio 3 * f( 3)+4* f(qui ho un dubbio devo fare 7 % 2 o il 3 che ho ottenuto prima????)
Grazie mille
X


public class Test{
public static void main(String[] args){

int x = 7;
int y = f(x);
System.out.println(y);
}

public static int f(int n){
if(n <= 1)
return 1;
else
return 3 * f(n / 2) + 4 * f(n % 2);
}
}

[LeleFT]

Quando tu effettui una chiamata ricorsiva, tutte le volte che compare la chiamata alla funzione viene passato, all funzione stessa, il valore ATTUALE del parametro.

Nel tuo caso, quindi si effettua questa chiamata:

return 3 * f(7 / 2) + 4 * f(7 % 2);


La sostituzione avviene in tutti i punti contemporaneamente, in base al valore attuale del parametro.


Ciao.

[xxx81xxx]

ok...grazie mille
quindi ricapitolando


return 3 * f(n / 2) + 4 * f(n % 2);

nel reurn avro' quindi

3*f(3)+4*f(1)

ora dato che ho 2 valori, nell'f() ,per ricominciare , quanto vale la x????

3 o 1 ?

[LeleFT]

Quando tu hai a che fare con chiamate ricorsive multiple, vengono generati tanti alberi di ricorsione quante sono le chiamate: in questo caso 2.

Il primo con n = 3 il secondo con n = 1

Il secondo termina subito, perchè la guardia dell'if (caso base) risulta verificata, quindi il secondo albero ritorna 1.

Il primo riparte: si avrà una seconda chiamata che genererà altri 2 alberi di ricorsione, uno con n = 1 ed il secondo uguale. Entrambi ritornano subito.

Risultato finale:

risultato = 3 * f(3) + 4 * f(1)

risultato = 3 * [3 * f(1) + 4 * f(1)] + 4 * 1

risultato = 9 + 12 + 4 = 25


Ciao.

[xxx81xxx]

capito...
fin troppo chiara come spiegazione!!!!!!
grazie 100000000