Difficoltà esercizio codice relativo al metodo ricorsivo
a)l'es. mi chiede di scrivere il codice relativo al metodo ricorsivo che, dato un parametro n>0, implementa la funzione f(n) = n + f(n-1). si assuma f(0). :
static void ricorsivo(int n) {
}
b)quanto restituisce il metodo quando viene chiamato con parametro di imput n=4??
svolgimento:
a) non lo so fare
b) ho considerato : f(4)= 4 + f(3)
f(3)=3 + f(2)
f(2)= 2 + f(1)
f(1)= 1 + f(0)
f(0)=0
chi mi aiuta?
static void ricorsivo(int n) {
}
b)quanto restituisce il metodo quando viene chiamato con parametro di imput n=4??
svolgimento:
a) non lo so fare
b) ho considerato : f(4)= 4 + f(3)
f(3)=3 + f(2)
f(2)= 2 + f(1)
f(1)= 1 + f(0)
f(0)=0
chi mi aiuta?
Risposte
Se nella traccia a, il testo ti da anche il prototipo della funzione da te scritta non puoi farlo.
Dato che, void (circa) = non ritorno nulla.
int n => passaggio per valore.
Come fai a sommare qualcosa che non ritorna e che la funzione non vedrà mai cambiare?
Dato che, void (circa) = non ritorno nulla.
int n => passaggio per valore.
Come fai a sommare qualcosa che non ritorna e che la funzione non vedrà mai cambiare?
Prima di preoccuparsi di come risolvere il particolare esercizio direi che è importante comprendere che cosa si intenda con ricorsione. Mi sembra infatti ti sia poco chiaro.
Partirei dalle funzioni ricorsive definite a partire da espressioni matematiche. Funzioni cioè il cui unico scopo è quello di restituire qualcosa che dipende in modo univoco dall'input della funzione stessa. Se definiamo infatti funzioni che stampano qualcosa o che modificano delle variabili membro o .. il discorso è leggermente diverso. Per definire una funzione ricorsiva di questo tipo dobbiamo definire due cose:
1. Una o più condizioni di terminazione a cui corrispondono determinati valori di ritorno della funzione. Nel tuo caso la condizione di terminazione è \( n = 0 \) e il valore che la funzione assume per questo valore dell'input è \(0\).
2. Una o più espressioni contenenti chiamate alla funzione per valori diversi dell'input per insiemi di input che non rispettano la condizione di terminazione. In questo caso c'è una sola espressione per ogni \( n \neq 0 \): \( f(n) = n + f(n-1). \)
Un esempio di funzione per cui ci sono più espressioni e condizioni di terminazione è:
\[ g(n) = \begin{cases} 0 & \text{se } n \leq 0 \\ 1 & \text{se } n = 1 \\ g(n / 2) + 5 & \text{se } n \text{ è pari} \\ g(n - 1)/2 & \text{se } n \text{ è dispari} \end{cases} \]
La userò come esempio in seguito.
Vediamo ora come si calcola il valore che la funzione assume per un qualche \( n_0 \) fissato (suppongo che la funzione abbia un solo parametro ma il discorso si può facilmente generalizzare). Per prima cosa si verifica se \( n_0 \) rispetta una qualche condizione di terminazione. Se la rispetta restituiamo il valore corrispondente della funzione. In caso contrario andiamo a cercare la definizione che corrisponde al valore \( n_0 \) e sostituiamo la funzione con la sua definizione (dove abbiamo sostituito \(n_0\) al posto della variabile corrispondente). Facciamo quindi tutti i calcoli che possiamo fare per semplificare la formula ottenuta e applichiamo questo stesso metodo a tutte le chiamate alla funzione fino ad ottenere un qualche valore. Per esempio, se scegliamo il valore \(5\) come partenza per la funzione ricorsiva descritta sopra, abbiamo:
\[ g(5) \to \frac{g(4)}{2} \to \frac{g(2) + 5}{2} \to \frac{g(1) + 5 + 5}{2} \to \frac{1 + 10}{2} \to \frac{11}{2} \]
Questo NON è il modo in cui linguaggi come Java o C o ... implementano la ricorsione. E' però il metodo più comodo per ottenere il valore corrispondente a mano (alcuni linguaggi utilizzano comunque qualcosa di simile).
Vediamo invece il tuo caso:
\[ f(4) \to 4 + f(3) \to 4 + 3 + f(2) \to 7 + 2 + f(1) \to 9 + 1 + f(0) \to 10 + 0 \to 10 \]
Credo sia quindi abbastanza chiaro che la funzione somma tutti i numeri da 0 a \(n\)..
Lo schema generale dell'implementazione di una funzione ricorsiva è
La funzione di esempio mostrata sopra potrà essere implementata come segue (è Java? sarebbe meglio se scrivessi il linguaggio..):
Ti lascio il compito di cercare di usare lo schema generale per cercare di implementare la tua funzione. Ti lascio inoltre il compito di calcolare g(7), g(24) e f(5) come esercizio per il punto b.
Partirei dalle funzioni ricorsive definite a partire da espressioni matematiche. Funzioni cioè il cui unico scopo è quello di restituire qualcosa che dipende in modo univoco dall'input della funzione stessa. Se definiamo infatti funzioni che stampano qualcosa o che modificano delle variabili membro o .. il discorso è leggermente diverso. Per definire una funzione ricorsiva di questo tipo dobbiamo definire due cose:
1. Una o più condizioni di terminazione a cui corrispondono determinati valori di ritorno della funzione. Nel tuo caso la condizione di terminazione è \( n = 0 \) e il valore che la funzione assume per questo valore dell'input è \(0\).
2. Una o più espressioni contenenti chiamate alla funzione per valori diversi dell'input per insiemi di input che non rispettano la condizione di terminazione. In questo caso c'è una sola espressione per ogni \( n \neq 0 \): \( f(n) = n + f(n-1). \)
Un esempio di funzione per cui ci sono più espressioni e condizioni di terminazione è:
\[ g(n) = \begin{cases} 0 & \text{se } n \leq 0 \\ 1 & \text{se } n = 1 \\ g(n / 2) + 5 & \text{se } n \text{ è pari} \\ g(n - 1)/2 & \text{se } n \text{ è dispari} \end{cases} \]
La userò come esempio in seguito.
Vediamo ora come si calcola il valore che la funzione assume per un qualche \( n_0 \) fissato (suppongo che la funzione abbia un solo parametro ma il discorso si può facilmente generalizzare). Per prima cosa si verifica se \( n_0 \) rispetta una qualche condizione di terminazione. Se la rispetta restituiamo il valore corrispondente della funzione. In caso contrario andiamo a cercare la definizione che corrisponde al valore \( n_0 \) e sostituiamo la funzione con la sua definizione (dove abbiamo sostituito \(n_0\) al posto della variabile corrispondente). Facciamo quindi tutti i calcoli che possiamo fare per semplificare la formula ottenuta e applichiamo questo stesso metodo a tutte le chiamate alla funzione fino ad ottenere un qualche valore. Per esempio, se scegliamo il valore \(5\) come partenza per la funzione ricorsiva descritta sopra, abbiamo:
\[ g(5) \to \frac{g(4)}{2} \to \frac{g(2) + 5}{2} \to \frac{g(1) + 5 + 5}{2} \to \frac{1 + 10}{2} \to \frac{11}{2} \]
Questo NON è il modo in cui linguaggi come Java o C o ... implementano la ricorsione. E' però il metodo più comodo per ottenere il valore corrispondente a mano (alcuni linguaggi utilizzano comunque qualcosa di simile).
Vediamo invece il tuo caso:
\[ f(4) \to 4 + f(3) \to 4 + 3 + f(2) \to 7 + 2 + f(1) \to 9 + 1 + f(0) \to 10 + 0 \to 10 \]
Credo sia quindi abbastanza chiaro che la funzione somma tutti i numeri da 0 a \(n\)..
Lo schema generale dell'implementazione di una funzione ricorsiva è
se gli argomenti rispettano una qualche condizione di terminazione
restituisce il valore corrispondente
altrimenti restituisci il valore ottenuto applicando la definizione corrispondente all'input
La funzione di esempio mostrata sopra potrà essere implementata come segue (è Java? sarebbe meglio se scrivessi il linguaggio..):
int g(int n) {
// verifica condizioni di terminazione..
// devono sempre essere le prime righe della tua funzione ricorsiva!!!
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
}
// caso generale non di terminazione
if (n % 2 == 0) {
return g(n / 2) + 5;
} else {
return g(n - 1)/2;
}
}
Ti lascio il compito di cercare di usare lo schema generale per cercare di implementare la tua funzione. Ti lascio inoltre il compito di calcolare g(7), g(24) e f(5) come esercizio per il punto b.
grazie... ma perchè si fa la somma??
nel punto b ho sbagliato perchè li avevo considerati singolarmente.
per il punto a dovrebbe essere cosi:
static void ricorsivo(int n) {
if( n == 0) {
return 0;
} else {
return n + ricorsivo(n-1);
}
}
???
nel punto b ho sbagliato perchè li avevo considerati singolarmente.
per il punto a dovrebbe essere cosi:
static void ricorsivo(int n) {
if( n == 0) {
return 0;
} else {
return n + ricorsivo(n-1);
}
}
???
static void [...] return n + ricorsivo(n-1);
Ti ripeto che un metodo void non può ritornare un valore intero.
Che intendi per "ma perchè si fa la somma??" ?
Ti ripeto che un metodo void non può ritornare un valore intero.
Che intendi per "ma perchè si fa la somma??" ?
\(n + f(n-1)\) significa che devi sommare il valore di \(f(n-1)\) ed \(n\). Quindi, una volta sviluppati i calcoli per tutti gli \(f(n)\) fino allo zero devi poi tornare indietro a sostituire il valore trovato per poter calcolare tutti gli \(f(i)\) con \(2 \leq i \leq n\). Cioè, prima calcoli \(f(1)\) a partire da \(f(0) = 0\) trovando che è uguale a \(1\). Poi calcoli \(f(2)\) trovando che è uguale a \(3\) e così via..
Il metodo deve restituire un int, ma per il resto è abbastanza corretto.
Il metodo deve restituire un int, ma per il resto è abbastanza corretto.
nessuno.nobody ti ha risposto apatriarca.
ok grazie ho capito
ok grazie ho capito
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo