[C] Algoritmo sul cubo di un numero

[Manugal]

Ciao a tutti!!!!

Non riesco a capire bene questo algoritmo ricorsivo. Il testo dice di assumere che esista una funzione quad() che calcoli il quadrato di un numero. Si deve quindi sviluppare una funzione cubo() che implementi un algoritmo ricorsivo che, usando solo somme e la funzione quad, restituisca il valore passato in input elevato al cubo. Il testo inoltre dice che bisogna usare lo sviluppo di (x+y)^3.

Lo sviluppo di questa lo so cioè è x^3+3x^2+3x+1. Sfruttando questo devo implementare l'algoritmo ricorsivo. Il mio prof l'ha sviluppato in questo modo:

int cubo(int x){
   if (x==0) return 0;
   else return cubo(x-1)+quad(x-1)+quad(x-1)+quad(x-1)+x+x+x-2;
}

Vorrei capire però come procede il programma ad ogni passo della ricorsione. In particolare vorrei capire qual'è proprio il valore dell'espressione ad ogni passo della ricorsione. Grazie.

[ilsensine]

Il tuo professore ha utilizzato l'identità

x^3 =
((x-1)+1)^3 =
(x-1)^3 + 3(x-1)^2 * 1 + 3(x-1) * 1^2 + 1^3 =
(x-1)^3 + 3(x-1)^2 + 3(x-1) + 1

calcolando quindi in maniera ricorsiva (x-1)^3, finché l'argomento del cubo non diviene 0 (e quindi anche il suo cubo).

[Manugal]

Ok questo l'ho capito, però vorrei capire come sono i vari passi della ricorsione.

[trallallero]

Originariamente inviato da Manugal

Ok questo l'ho capito, però vorrei capire come sono i vari passi della ricorsione.

Ti faccio vedere un esempio ... penso ci sia passato chiunque dal calcolo del fattoriale con la ricorsione ...

int Fattor( int i )
{
   if (i)
      i += Fattor( --i );

   return i;
}

la funzione chiama se stessa fino a quando i > 0
la si puo' vedere cosi passando per ex 4:
andata:
Fattor(4)
...Fattor(3)
......Fattor(2)
.........Fattor(1)
ritorno:
.........i += 1
......i += 2
...i += 3
i += 4

that's all
lo applichi al tuo problema e il gioco e' fatto

[ilsensine]

Originariamente inviato da Manugal

Ok questo l'ho capito, però vorrei capire come sono i vari passi della ricorsione.

"cubo" viene invocata per tutti i valori di x da quello iniziale fino a 0:

cubo(x) = cubo(x-1)+2quad(x-1)+3x-2;
dove (calcolato ricorsivamente)
cubo(x-1) = cubo(x-2)+2quad(x-2)+3(x-1)-2;
dove
cubo(x-2) = cubo(x-3)+2quad(x-3)+3(x-2)-2;
dove
...
dove
cubo(2) = cubo(1)+2quad(1)+3*2-2;
dove
cubo(1) = cubo(0)+2quad(0)+3*0-2;
dove
cubo(0) = 0 (condizione di uscita)

Nota che la condizione di uscita è arbitraria, e rappresenta un valore per cui il cubo è noto e che ti consente di terminare la ricorsione. Andava ugualmente bene definire la funzione in questa maniera:

int cubo(int x){
   if (x==-3) return -27;
   else return cubo(x-1)+quad(x-1)+quad(x-1)+quad(x-1)+x+x+x-2;
}

[Manugal]

Ok ora ho capito grazie