Simbolo "%" e sua funzione.

[Klibion]

Nel seguente esercizio, comparso in un test scritto, mi veniva richiesto che cosa avrebbe stampato la macchina! Purtroppo ho sbagliato a dare le risposte e oggi, provandolo al computer, ricevo in stampa dati che non mi so spiegare! Soprattutto mi crea difficoltà il simbolo %, che non riesco ancora a comprendere bene. Sapevo che indicava il resto di una divisione e in questo caso, il numero della divisione per 2, con resto 0, ma anche con questa informazione non so spiegarmi i risultati. Qualcuno mi aiuta?

public class Mainclass {

public static void main(String[] args) {

System.out.println(enigma(1));
System.out.println(enigma(6));
System.out.println(enigma(10));
System.out.println(enigma(11));
}

static int enigma (int x){

if (x<=0) return 0;

if (x%2==0) return enigma(x-1) + x;
return enigma (x-1) - x;
}
}

RISULTATO DI STAMPA:

-1
3
5
-6

[andbin]

Soprattutto mi crea difficoltà il simbolo %, che non riesco ancora a comprendere bene. Sapevo che indicava il resto di una divisione e in questo caso, il numero della divisione per 2, con resto 0

L'operatore % è il resto della divisione. Quindi if (x%2==0) vuol dire una cosa semplice: "se x è pari". Stop, tutto qui.

ma anche con questa informazione non so spiegarmi i risultati.

Il punto è che quel metodo enigma è "ricorsivo", quindi il problema non è tanto il "resto" della divisione ma comprendere e seguire la ricorsione. Data la prima invocazione es. di enigma(6) devi ragionare e "scendere" man mano nei vari eventuali livello di ricorsione.

enigma(6): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(5)+6
enigma(5): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(4)-4
ecc...

Quando si arriva al livello per cui non c'è più ricorsione, si ritorna indietro dalle varie invocazioni e quindi si applica quel + o - arrivando poi al risultato finale.

Suggerimento: continua a valutare con l'esempio detto poco fa.

[Klibion]

Allora evidentemente non ho compreso bene la ricorsione! Da quanto ho capito la ricorsione si usa quando bisogna affrontare calcoli complessi come i fattoriali o la sucessioni di fibonacci. In poche parole sospende il metodo principale, esegue quello invocato e poi conclude il tutto.

In questo caso passo al metodo principale una variabile X dal valore prestabilito. Per far un esempio concreto, prendo in esame il valore "6". Partendo dal fatto che tutti i valori dell'esercizio sono maggiori di 0 e che quindi il metodo non ritornerà mai all'inizio, prendo in considerazione i seguenti passaggi:

if (x%2==0) return enigma(x-1) + x;
=> significa che se il resto della divisione è 0 e che quindi X è pari, devo ritornare il metodo con (x-1) + x:
Ergo se il numero scelto è 6 devo fare (6-1)+6=11

return enigma (x-1) - x;
}
=> questo passaggio viene saltato e si passa alla stampa che è 11!
MA a me viene 3 non 11, perché?

[andbin]

Allora evidentemente non ho compreso bene la ricorsione! Da quanto ho capito la ricorsione si usa quando bisogna affrontare calcoli complessi come i fattoriali o la sucessioni di fibonacci.

Nì. Allora: innanzitutto un certo algoritmo lo si può implementare sia in modo "ricorsivo" che in modo "iterativo". È possibile convertire un approccio ricorsivo in uno iterativo e viceversa.
Poi chiaramente ci sono concetti e logiche che sono più facilmente esprimibili con la ricorsione e altri più facilmente esprimibili in modo iterativo.

In poche parole sospende il metodo principale, esegue quello invocato e poi conclude il tutto.

La ricorsione termina quando ad un certo livello di invocazione del metodo, c'è una qualche condizione per cui il metodo NON invoca più sé stesso. Ma ci deve appunto essere questa condizione, altrimenti andrebbe in loop continuo.

In questo caso passo al metodo principale una variabile X dal valore prestabilito. Per far un esempio concreto, prendo in esame il valore "6". Partendo dal fatto che tutti i valori dell'esercizio sono maggiori di 0 e che quindi il metodo non ritornerà mai all'inizio, prendo in considerazione i seguenti passaggi:

Qualcuno invoca inizialmente enigma(6) (non importa ora dove/come). Siccome 6 è pari, viene eseguito solo il

return enigma(x-1) + x;

Ma enigma(x-1) vuol dire: x è 6, si sottrae 1 (senza modificare la variabile x) e quindi viene fatta una NUOVA invocazione di enigma passando appunto 5.


enigma(6): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(5)+6
enigma(5): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(4)-4
....CONTINUA TU....

[Klibion]

Non sapevo che si potesse convertire un approccio iterativo con uno ricorsivo, anche se effettivamente più o meno applicano lo stesso ragionamento d'azione.

Sia le ricorsioni che le iterazioni continuano finché una determinata condizione è verificata, altrimenti vanno a conclusione e questo lo sapevo.

Ora però quel -4 che hai scritto, da dove è uscito?
enigma(6): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(5)+6 = 11
enigma(5): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(4)-5 = -1
enigma(4): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(3)+4 = 7
enigma(3): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(2)-3 = -1
enigma(2): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(1)+2 = 3
enigma(1): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(0)-1 = -1

E quindi? non concludo niente comunque. Con l'invocazione del metodo (6) non ottengo mai 3

[Ansharja]

Non sapevo che si potesse convertire un approccio iterativo con uno ricorsivo, anche se effettivamente più o meno applicano lo stesso ragionamento d'azione.

Sia le ricorsioni che le iterazioni continuano finché una determinata condizione è verificata, altrimenti vanno a conclusione e questo lo sapevo.

Ora però quel -4 che hai scritto, da dove è uscito?
enigma(6): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(5)+6 = 11
enigma(5): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(4)-5 = -1
enigma(4): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(3)+4 = 7
enigma(3): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(2)-3 = -1
enigma(2): non è <=0 quindi NON fa return 0. È pari, quindi il return sarà di enigma(1)+2 = 3
enigma(1): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(0)-1 = -1

E quindi? non concludo niente comunque. Con l'invocazione del metodo (6) non ottengo mai 3

Quel -4 penso fosse un -5, in effetti enigma (5) restituirà enigma (4) - 5 come hai scritto tu.

Attento però : è corretto che enigma (6) faccia 3, stai effettuando delle somme sbagliate, enigma (5) + 6 non fa 11.

enigma (6) prima richiama enigma (5), poi aggiungerà al risultato della ricorsione 6, ma solo a ricorsione conclusa.
A sua volta enigma(5) andrà un livello in basso e così via.

Quindi il primo metodo che terminerà sarà enigma (0), che restituisce 0.

Quindi :

enigma (1) = enigma (0) - 1 = -1.
enigma (2) = enigma (1) + 2 = -1 + 2 = 1.
enigma (3) = enigma (2) - 3 = 1 - 3 = -2.
enigma (4) = enigma (3) + 4 = -2 + 4 = 2.
enigma (5) = enigma (4) - 5 = 2 - 5 = -3.
enigma (6) = enigma (5) + 6 = -3 + 6 = 3.

Se vuoi partire dal 6, devi proseguire per sostituzioni successive :

enigma (6) = enigma (5) + 6 = enigma (4) - 5 + 6 = enigma (3) + 4 - 5 + 6 = ...

Comunque quando non riesci a seguire bene il flusso o non trovi un errore in un programma, la prima cosa banale che ti deve venire in mente è di mettere dei print qua e là che ti stampino i valori delle variabili di interesse.

Se ad esempio come prima istruzione in enigma tu scrivessi :

System.out.println ("Entro nel metodo enigma con x = " + x);

Avresti nell'output il percorso completo che fa la ricorsione

[andbin]

enigma(1): non è <=0 quindi NON fa return 0. È dispari, quindi il return sarà di enigma(0)-1 = -1

E quindi?

E quindi l'ultima invocazione è enigma(0), e siccome c'è quel

if (x<=0) return 0;

il risultato è SUBITO 0. Questa è la condizione di "terminazione" che dicevo prima. In questo caso quindi enigma NON viene invocato ricorsivamente.

Pertanto: enigma(0) restituisce subito 0 e non fa altro. Ora si torna indietro, uscendo man mano da tutta la catena di invocazioni di enigma.

Quindi:
enigma(0)-1 ----> 0-1 = -1

Siccome era stato chiamato enigma(1), ora sappiamo che vale -1, quindi

enigma(1)+2 ----> -1+2 = +1

e così via. Fai i passi indietro e risolvi quindi quella espressione ora che sai ciascun valore ritornato dal livello sottostante!


P.S. guardalo idealmente anche dal punto di vista "grafico".

        enigma(6)
       /         \
      /           \
      enigma(5) + 6
     /         \
    /           \
    enigma(4) - 5
   /         \
  /   .....   \

[Klibion]

PERFETTO! Grazie mille