ho un problema relativo al meccanismo di ricorsione, che non riesco proprio a capire....
Nelle mie dispense vengono elencati i seguenti tipi di ricorsione, provo a spiegare quello che ho capito per farvi capire dove mi confondo:
1) Ricorsione 'base': da quel che ho capito si tratta di un metodo che richiama se stesso in un caso più semplice da risolvere e via via più vicino al caso 'base', noto per definizione.
--> quindi si tratta di una funzione definita da clausole del tipo: - F(0) = a; - F(x) = E(F(x-1)), ovvero per calcolare F(x) posso usare una funzione con argomento più piccolo, alla quale si applica una determinata espressione che permette di passare da un caso all'altro.
2) Ricorsione 'controvariante': si tratta di un metodo che implementa un parametro in più che cresce fino a raggiungere un determinato valore che costituisce il caso 'base' visto nella ricorsione precedente.
--> es. nel caso della sottrazione è una funzione definita dalle clausole:
- meno (m, n, n) = m;
- meno (m, n, p) = meno (m, n, p+1) -1
e cioè calcola m -n utilizzando un terzo parametro p che cresce da 0 fino al caso base m=n e restituisce m, al quale vengono sottratte quantità di 1 tante volte quanto gli step necessari affinché p raggiunga il valore n
P.S: in questo tipo di ricorsione viene definito un metodo particolare, detto wrapper, che ha lo scopo di evitare l'innesco della ricorsione per casi in cui essa non può essere definita, del tipo:
Testo nascosto, fai click qui per vederlo
- Codice:
public static int meno(int m, int n) {
if (m < n) {
return 0;
}
else {
return meno(m, n, 0);
}
}
private static int meno(int m, int n, int p) {
if (p == n) {
return m;
}
else {
return meno(m, n, p + 1) - 1;
}
}
3) Ricorsione 'di coda': questo è il problema principale, non riesco a capire la differenza con quella 'controvariante'...
Due codici di esempio che sono usati nelle dispense:
//Calcolo della moltiplicazione tra due numeri come iterazione di somme
Testo nascosto, fai click qui per vederlo
- Codice:
/**
* Trasposizione ricorsiva di coda di {@code MoltiplicazioneSommaIterata}.
*/
public class mXYRecCoda {
/**
* Prodotto tra {@code x} e {@code y}.
*/
public static int mXY(int x, int y) {
return mXY(x, y, 0, y);
}
private static int mXY(int x, int y, int r, int k) {
/*
* l'ipotesi induttiva e' che i valori assegnati ai parametri formali x,
* y, r e k soddisfino la seguente equazione: x * y == r + (x * k)
*/
if (k == 0)
/*
* se k e' nullo allora x * y == r + (x * k) == r e possiamo
* restituire il valore che esso contiene perche' quello cercato.
*/
return r;
else
/*
* se k non e' ancora nullo, ci comportiamo come nel caso iterativo:
* riversiamo un x in r e togliamo (contemporaneamente) una unita'
* da k. Quindi i valori che assumeranno i parametri x, y, r, e k
* nel frame di sXY(x, y, r + x, k - 1) saranno ancora quelli
* corretti: x + y == (r + x) + x*(k - 1) == r + (x * k)
*/
return mXY(x, y, r + x, k - 1);
}
public static void main(String[] args) {
for (int x = 1; x < 10; x++)
for (int y = 0; y < 10; y++)
System.out.println(mXYRec.mXY(x, y) == mXY(x, y));
}
}
// Calcolo della media tra un numero arbitrario di valori
Testo nascosto, fai click qui per vederlo
- Codice:
/**
* Legge {@code n} interi e ne calcola la media, usando un metodo ricorsivo di
* coda per restituire la media al termine della ricorisione.
*/
public class MediaRecCoda {
public static float media(int k, int n, int somma) {
if (k == 0) {
return (float) somma / n;
} else {
System.out.println("Numero?");
int numero = SIn.readInt();
return media(k - 1, n, somma + numero);
}
}
public static void main(String[] args) {
System.out.println("Di quanti numeri calcolare la media?");
int n = SIn.readInt();
float media = media(n, n, 0);
System.out.println("La media e' " + media + ".");
}
}
Nello specifico, come mai nel primo metodo viene utilizzato il wrapper come nella ricorsione controvariante mentre nel secondo non è utilizzato, pur essendo lo stesso tipo di ricorsione?
Che differenza c'è tra la ricorsione controvariante e quella di coda?
Vi ringrazio in anticipo e scusate per il lungo messaggio, ho provato a riassumere nel miglior modo possibile senza tralasciare dettagli
