DOMANDA Meccanismo di ricorsione

[FS96]

Buongiorno a tutti,
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:

Spoiler

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

Spoiler

/**
* 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

Spoiler

/**
* 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

 

[icox]

Il metodo "controvariante" e' la prima volta che lo sento, se ho capito cosa intende il tuo testo/professore si differenzia con la ricorsione di coda nel fatto che la prima fa una serie di chiamate ricorsive fino ad arrivare al caso base (svolgendo le operazioni man mano che "scende"), mentre nella ricorsione di coda prima avviene la "discesa" e le varie istruzioni vengono eseguite "al ritorno" quando i metodi terminano e vengono deallocati.

Un esempio di ricorsione "di coda" potrebbe essere nel calcolo di una certa espressione in cui ogni termine della ricorsione deve essere valutato sulla base del passo successivo: l'unico modo per sapere quale sara' il valore successivo e' effettuare la chiamata ricorsiva, quindi la valutazione del risultato la fai quando questa "ritorna".
Al contrario, ci sono casi in cui la decisione su quale istruzione seguire dipende dal valore attuale che una certa variabile/i, quindi le istruzioni vengono eseguite prima di effettuare una nuova chiamata.

Torna?

 

[DispatchCode]

Mi associo al pensiero di icox.
Deduco che le terminologie utilizzate non siano utilizzate nel gergo standard.

Detto in modo "maccheronico" penso li intenda solo come differenze di implementazione, una parte dal basso e una dall'alto, in pratica.
Tuttavia il meccanismo ricorsivo in sé è sempre lo stesso, si tratta pur sempre di uno stack di chiamate.
Normalmente il caso base è il passo più semplice semplice possibile ed è indispensabile come condizione di uscita (e quindi di ritorno al chiamante, che in caso di ricorsione è la medesima funzione, ma al passo precedente e così via).