[C]: Algoritmo ricorsivo su 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 perché usare tutta questa miriade di operazioni e come procede il programma ad ogni passo della ricorsione. Grazie

[fastcoder]

Di matematica non ne capisco molto ma se lo sviluppo di X^3=(X-1)^3+3*(X-1)^+3*X+1
in teoria vuol dire che X^3 lo ricavi da (X-1)^3, inoltre 0^3 = 0...se questo l'ho capito bene
allora l'algoritmo ricorsivo è esattamente quello del tuo prof. Il fatto di tutti quei calcoli è che non puoi usare la moltiplicazione ma solo la somma...quindi 3*(x-1)+1=3x-3=x+x+x-2.
In pratica per 3^3 succederebbe:
- x non è zero quindi faccio cubo(2)+....
- quindi richiamo cubo(2)
- x non è zero quindi faccio cubo(1)+...
- quindi richiamo cubo(1)
- x non è zero quindi faccio cubo(0)+...
- quindi richiamo cubo(0)
- ora x è zero quindi ritorno zero a chi mi ha chiamato cioè cubo(1)
- continuo quello che avevo interrotto in cubo(1) cioè il calcolo cubo(1)+... usando però
il valore di ritorno di cubo(0) che era zero, poi restituisco il calcolo con la return a cubo(2)
- e così via fino a ritornare dalla funzione con il calcolo di 3^3.

[Manugal]

Ok grazie ma quello che non capisco è il valore che l'intera espressione assume ad ogni passo della ricorsione.

[fastcoder]

L'espressione assume i valori durante la fase di backtraking ed in particolare assume i valori
nell'ordine, cubo(3):
- 0+quad(0)+quad(0)+quad(0)+0+0+0-2 (ritorno da cubo(1))
- (0+quad(0)+quad(0)+quad(0)+0+0+0-2) + quad(1)+quad(1)+quad(1)+1+1+1-2 (ritorno da cubo(2))
- ((0+quad(0)+quad(0)+quad(0)+0+0+0-2) + quad(1)+quad(1)+quad(1)+1+1+1-2)+quad(2)+quad(2)+quad(2)+2+2+2-2 (ritorno da cubo(3)

Almeno spero

[Manugal]

Dato che la return è questa:

return cubo(x-1)+quad(x-1)+quad(x-1)+quad(x-1)+x+x+x-2

il ritorno da cubo(1) non dovrebbe essere 0+quad(0)+quad(0)+quad(0)+3+3+3-2? Le ultime tre x prima di -2 nell'espressione non sono parametri della ricorsione. Cmq facendo il calcolo dell'espressione non viene quanto dovrebbe venire (infatti il cubo di 3 è 27).

[fastcoder]

Si...probabilmente ho fatto qualche casino con le x
Rifacciamo:
A- chiamo cubo(3)
B- chiamo cubo(2)
C- chiamo cubo(1)
D- chiamo cubo(0)
D- ritorno 0
C- ritorno 0+quad(0)+quad(0)+quad(0)+1+1+1-2
B- ritorno 1+quad(1)+quad(1)+quad(1)+2+2+2-2
A- ritorno 8+quad(2)+quad(2)+quad(2)+3+3+3-2
quindi ho 8+12+9-2=27

OK ci siamo

[Manugal]

Ti giuro i problemi che magari sembrano più difficili riesco a farli con più "naturalezza", ma ci sono certi problemi "banali" come questo che mi fanno sbattere la testa per ore

Cmq grazie mille. Un'ultima cosa, perché nell'espressione anche le 3 x prima di -2, durante la ricorsione, si decrementano di 1?

[fastcoder]

Si decrementano per via della chiamata ricorsiva cubo(x-1) in testa all'espressione della return. Sono decrementate di uno solo nella nuova chiamata ovviamente. Purtroppo non chiedermi la ragione matematica perchè io l'accetto per fede
Non credo che si possano definire problemi banali o complessi in assoluto: dipende dal momento...anche io incontro problemi che per me sono complicatissimi e una volta capiti si trasformano in banalità...dipende dal momento

[Manugal]

Capito... grazie mille!!