View Full Version : [C++] Problema ricorsione
Ciao a tutti. Sto provando a scrivere una funzione ricorsiva che, dato un array di interi, cerchi il primo multiplo di un intero n dato in input dall'utente e ne restituisca la posizione dell'array. So bene che usando un ciclo for sarebbe una cazzata, ma mi serve fare esercizio sulla ricorsione. Vi copio di seguito il codice, potete aiutarmi?
using namespace std;
#include<iostream>
int ricerca(int a[], int dim, int n, int& pos);
int main(){
int n, pos, res;
pos=0;
const int SIZE=6;
int array[SIZE]={3,2,4,6,8,9};
cout << "Di che numero vuoi cercare il primo multiplo?" << endl;
cin>>n; //inserimento del numero di cui cercare il primo multiplo
res=ricerca(array,SIZE,n,pos);
if(res==-1){
cout << "Non ci sono multipli di " << n << endl;
}
else cout << "Il primo multiplo di " << n << " è " << array[pos] << " e si trova alla posizione " << res << endl;
}
int ricerca(int a[], int dim, int n, int& pos){
int i=0;
if(i<=dim){
if(a[i]%n==0) {pos=i;}
else{
pos=-1;
i++;
ricerca(a,dim,n,pos);
}
}
else return pos;
}
Se poi avete qualche consiglio da dare sulla ricorsione in generale fate pure, è un argomento che mi crea ancora qualche problema. :D
Un consiglio che ti posso dare sulla ricorsione è questo: hai presente come si fanno le dimostrazioni per induzione ? Per risolvere facilmente i problemi di ricorsione devi operare nello stesso modo.
Prima gestisci la condizione di arresto, ora sai che il tuo codice non fa la ricorsione, ma sicuramente si arresterà.
Ora pensa al generico elemento sul quale dovrai effettuare la ricorsione, non pensare agli elementi che ci sono e non pensare agli elementi che ci sono dopo.
Esegui prima di tutto l'elaborazione dell'elemento corrente (non importa se in realtà dovrai metterla in un altro punto, te ne occuperai dopo).
A questo punto pensa alle condizioni di ricorsione, in quale caso, in base alle informazioni del passo corrente, dovrai effettuare la ricorsione su un elemento successivo o su un altro elemento successivo oppure semplicemente non effettuare alcuna ricorsione (come al solito non ti preoccupare degli elementi successivi, ma ragiona solo in base all'elemento corrente).
Ora scrivi le condizioni che hai pensato sotto forma di if (per non effettuare la ricorsione usa il return).
Manca solo da posizionare l'elaborazione dell'elemento corrente, fatti un piccolo esempio scrivendoti a mano dei dati di prova e verifica dove spostare l'elaborazione dell'elemento per ottenere quello che vuoi come risultato. A costo di provare tutte le combinazione che spesso sono solo tre o anche meno sono sicuro che ci riuscirai.
A questo punto automaticamente funziona tutto. L'errore che spesso si fa è proprio pensare a quello che succede agli elementi successivi o precedenti in base alle decisioni prese per l'elemento corrente. Questo modo di pensare non è lineare perché le condizioni da prendere in esame si moltiplicano sempre più.
Quindi pensa solo a quello che devi fare con l'elemento corrente e alle condizioni di ricorsione in base all'elemento corrente ed otterrai il risultato, certe volte, ti assicuro, quasi automaticamente.
Te lo dico perché all'università insegnai questo metodo a molti dei miei compagni che avevano problemi con la ricorsione e furono davvero soddisfatti.
Quella funzione che hai scritto può essere molto, ma molto più semplice ;)
Riallacciandomi al discorso sopra: la/le condizione/condizioni di arresto le devi scrivere in questo modo
if(condizione)
return;
Ti renderà la vita più facile. Ovviamente nel caso sopra devi ritornare anche un valore.
Nell'esercizio sopra hai due condizioni di arresto:
-arrivi in fondo al vettore
-hai trovato un elemento valido
!k-0t1c!
10-06-2009, 20:01
Io lo farei così, ma non è stupendo.
Per fare le cose per bene dovresti usare la ricerca binaria, assumendo ovviamente che tu non voglia la prima occorrenza del valore o che ogni valore compaia una sola volta.
Considera inoltre che nel C++ (e nel C99) non è affatto obbligatorio dichiarare tutte le variabili in cima alla funzione, ed è pratica comune dichiararle al momento dell'inizializzazione.
Nota inoltre che con un array sufficientemente grande lo stack overflow sarebbe inevitabile. In generale la ricorsione non è un buon approccio nei linguaggi che non supportano la tail recursion e pertanto si ricorre sovente al fatto che ogni funzione ricorsiva può essere scritta in forma non ricorsiva.
int ricerca(int * a, int dim, int n)
{
if(dim > 0)
{
if(a[0] % n == 0) return dim;
else return ricerca(a+1, dim-1, n);
}
return 0;
}
//nel main
int res = ricerca(array, SIZE, n);
if(res != 0)
{
res = SIZE - res; //ora res contiene la posizione
}
else
{
//il numero non è stato trovato, gestisci il caso
}
Cory: per ora non guardare le soluzioni proposte, prova a pensare a quello che ti ho detto e scrivi le due condizioni di arresto ;)
!k-0t1c!
11-06-2009, 00:50
int multiple(int *array, int dim, int value)
{
if (!(*array % value) || !dim )
{
return 0;
}
else return 1 + multiple(array+1,dim-1,value);
}
io farei una cosa del genere... restituisce l'indice se lo trova altrimenti restituisce il primo indice non valido (se fornisci un array di 4 elementi e non trova un multiplo, restituisce l'indice 4, cioè il primo non valido). ciao ;)
E' una soluzione rischiosa. Se un compilatore implementa la tail recusion o qualche altra forma di ottimizzazione in caso di funzioni ricorsive con questo codice gli tarpi le ali perché bisogna attendere il valore della chiamata ricorsiva. Diciamo che nella programmazione funzionale, dove la ricorsione è all'ordine del giorno, questo codice non sarebbe visto affatto di buon occhio :cool:
Un consiglio che ti posso dare sulla ricorsione è questo: hai presente come si fanno le dimostrazioni per induzione ? Per risolvere facilmente i problemi di ricorsione devi operare nello stesso modo.
Prima gestisci la condizione di arresto, ora sai che il tuo codice non fa la ricorsione, ma sicuramente si arresterà.
Ora pensa al generico elemento sul quale dovrai effettuare la ricorsione, non pensare agli elementi che ci sono e non pensare agli elementi che ci sono dopo.
Esegui prima di tutto l'elaborazione dell'elemento corrente (non importa se in realtà dovrai metterla in un altro punto, te ne occuperai dopo).
A questo punto pensa alle condizioni di ricorsione, in quale caso, in base alle informazioni del passo corrente, dovrai effettuare la ricorsione su un elemento successivo o su un altro elemento successivo oppure semplicemente non effettuare alcuna ricorsione (come al solito non ti preoccupare degli elementi successivi, ma ragiona solo in base all'elemento corrente).
Ora scrivi le condizioni che hai pensato sotto forma di if (per non effettuare la ricorsione usa il return).
Manca solo da posizionare l'elaborazione dell'elemento corrente, fatti un piccolo esempio scrivendoti a mano dei dati di prova e verifica dove spostare l'elaborazione dell'elemento per ottenere quello che vuoi come risultato. A costo di provare tutte le combinazione che spesso sono solo tre o anche meno sono sicuro che ci riuscirai.
A questo punto automaticamente funziona tutto. L'errore che spesso si fa è proprio pensare a quello che succede agli elementi successivi o precedenti in base alle decisioni prese per l'elemento corrente. Questo modo di pensare non è lineare perché le condizioni da prendere in esame si moltiplicano sempre più.
Quindi pensa solo a quello che devi fare con l'elemento corrente e alle condizioni di ricorsione in base all'elemento corrente ed otterrai il risultato, certe volte, ti assicuro, quasi automaticamente.
Te lo dico perché all'università insegnai questo metodo a molti dei miei compagni che avevano problemi con la ricorsione e furono davvero soddisfatti.
madò, grande! Sì, ho presente come si fanno le dimostrazioni per induzione, proverò a fare così!!
Se ti va puoi mandarmi (anche in pm) qualche esercizio o link a esercizi sulla ricorsione? Ho un qualche tipo di "Lack of Comprehension" :D
Parti da questo esercizio, scrivimi le condizioni di arresto, poi ti insegno anche qualche trucchetto, questo esercizio si presta bene ;)
dunque vediamo...
int ricerca(int a[], int dim, int n, int& pos){
int i=0;
if(a[i]%n==0) {pos=i; return pos;}
}
/*parto assumendo che il primo elemento dell'array sia multiplo di n. In questo caso ho finito, quindi non serve che vada in ricorsione sul resto dell'array e restituisco direttamente l'indice */
i casi che mi si possono presentare restano quindi due: 1) che ci sia un multiplo di n nel resto dell'array 2) che non ci sia nessun multiplo di n. Nel caso
/* nel primo caso incremento quindi l'indice i, facendo attenzione che sia al più uguale alla dimensione dell'array -1. Poi richiamo la funzione.*/
i++;
if(i<dim) return ricerca(array, SIZE, dim, pos);
/*Infine, se nell'array non è presente nessun tipo di multiplo di n, assegno a pos il valore -1.*/
else pos=-1;
return pos;
Quante cazzate ho sparato?
Intanto quella i messa così non va bene perché ad ogni ricorsione viene azzerata.
Non usare if else, espirimi le condizioni di arresto in funzione di i e dim.
Solo nella forma:
if(condizione)
return X;
Ovviamente al posto di X devi mettere la cosa giusta. Facciamo che la funzione ritorni l'indice in caso di valore trovato e -1 altrimenti.
Intanto quella i messa così non va bene perché ad ogni ricorsione viene azzerata.
ah cazzo...ecco perchè mi dava segmentation fault...quindi mi tocca per forza di cose andare a modificare qualche parametro della funzione.
int ricerca(int a[], int dim, int n, int& pos, int index){
if(index<dim){
if(a[index]%n==0){pos=index; return pos;}
else return ricerca(array,SIZE,n,pos,index++);
}
}
mi manca da definire che fare se nell'array non ci sono multipli di n...
Cory, ripeto scrivi le condizioni di arresto della ricorsione PRIMA ed in questa forma:
if(condizione)
return;
if(a[i]%n==0) pos=i; return i;
/*se l'elemento è multiplo restituisce l'indice ed esce dalla funzione */
if(a[i]%n!=0) pos=-1; return pos;
/*l'elemento non è multiplo, quindi vado in ricorsione sul resto dell'array */
boh, non so come continuare..
No è sbagliato.
Ripeti quali sono le condizioni per cui si fa la ricorsione (condizioni di arresto) e quali sono le condizioni per cui si fa la ricorsione.
E' inutile mettere i in pos perché tanto già ritorni la posizione con return.
uff non ci capisco un cazzo
uff non ci capisco un cazzo
Ricapitolando: quando si deve effettuare la ricorsione ? Quando non ho trovato un elemento multiplo di altri, quindi devo passare al successivo. Ti torna ?
Quali sono invece le condizioni di arresto ?
La prima è quella in cui arrivo in fondo al vettore e ritorno -1.
La seconda è quella in cui trovo un elemento multiplo di un altro e ritorno l'indice index.
Ci siamo o no ?
Esprimi le condizioni di arresto sotto forma di codice usando if e return per ogni condizione.
Ricapitolando: quando si deve effettuare la ricorsione ? Quando non ho trovato un elemento multiplo di altri, quindi devo passare al successivo. Ti torna ?
Quali sono invece le condizioni di arresto ?
La prima è quella in cui arrivo in fondo al vettore e ritorno -1.
La seconda è quella in cui trovo un elemento multiplo di un altro e ritorno l'indice index.
Ci siamo o no ?
Esprimi le condizioni di arresto sotto forma di codice usando if e return per ogni condizione.
sì, fino a qui ci sono..solo che non so cosa mettere come return.
if(a[i]%n==0) return i;
if(i==dim-1) pos=-1; return pos;
boh
pos non ti serve, non ce lo devi mettere perché ritorni già -1, togli pos dal prototipo della funzione.
if(a[i]%n==0) return i;
if(i==dim-1) return -1;
A questo punto ti trovi al passo i-esimo nella situazione in cui devi effettuare la ricorsione.
Scrivi la ricorsione, ricordando che non ci sono condizioni per la ricorsione quindi devi semplicemente passare la ricorsione sull'elemento successivo. In questo caso non c'è nemmeno alcuna elaborazione da fare sui dati.
Guarda che l'avevi già scritto prima il codice corretto per questa parte.
~FullSyst3m~
11-06-2009, 12:58
cionci sai che è stato illuminante il tuo primo post (e anche il ragionamento a "pezzi" che hai fatto successivamente)? Sinceramente la spiegazione mi è sembrata un pochettino confusionaria, ma sicuramente è più chiara di un codice che ho trovato che mi ha fatto mettere le mani nei capelli.
Credevo di averla capita la ricorsione, ma quando ho visto questo codice dopo 4 righe mi sono bloccato, una cosa orrenda. Cosi mi chiedo se l'abbia capita davvero o no la ricorsione.
Se lo ritrovo posto il codice (è in Python).
Sinceramente la spiegazione mi è sembrata un pochettino confusionaria
Ah sì, questo è poco ma sicuro :D E' difficile mettere in piedi un discorso di quel tipo senza esempi di codice.
Un esercizio secondo che mette molto meglio in evidenza quello che voglio dire è ad esempio la ricerca dell'ultimo elemento del vettore che è mutiplo di un valore (supponiamo che sia obbligatorio partire a controllare dall'elemento zero e non sia possibile partire dall'ultimo, la cosa sarebbe obbligatoria in una lista singolarmente linkata).
~FullSyst3m~
11-06-2009, 13:29
Ah sì, questo è poco ma sicuro :D E' difficile mettere in piedi un discorso di quel tipo senza esempi di codice.
Un esercizio secondo che mette molto meglio in evidenza quello che voglio dire è ad esempio la ricerca dell'ultimo elemento del vettore che è mutiplo di un valore (supponiamo che sia obbligatorio partire a controllare dall'elemento zero e non sia possibile partire dall'ultimo, la cosa sarebbe obbligatoria in una lista singolarmente linkata).
E' stata una bella "sensazione" però vedere aprirsi altri punti di vista, alla fin fine la ricorsione l'ho studiata scrivendo le varie chiamate su carta e penna e facendomela spiegare al volo da cdimauro quando l'ho incontrata mentre studiavo Python. Però quando ho visto quel codice del quale parlavo prima mi è venuto il dubbio se l'ho capita davvero o meno. O sono io o è il codice. Non ci sono alternative.
così potrebbe andare? purtroppo non mi da il risultato che volevo
int ricerca(int a[], int dim, int n, int pos){
if(pos>dim){
return -1;
}
else{
if(a[pos]%n==0) return pos;
else return ricerca(array,SIZE,n,pos++);
}
}
nel senso che, giustamente,mi dice che array e SIZE non sono definiti nello scope.
Cory: perché ogni volta torni indietro ?
Parti da qui:
if(a[i]%n==0)
return i;
if(i==dim-1)
return -1;
Ti ho già detto che non ci sono condizioni (if) per la ricorsione, basta solo scrivere la regola di ricorsione.
Nota: che quella sopra può anche andare bene, cambiando qualche nome alle variabili, ma ti sei nuovamente perso fra if ed else.
Sia chiaro che catene di if else possono andare, questa volta il codice è facile, ma non ti permettono di SEPARARE le varie parie parti.
scusa, ma tu come lo faresti?? perchè più che quello che ho scritto sopra non saprei che diavolo fare..
Il tuo codice in fondo va anche bene è la forma in cui l'ha scritto che per una situazione più complessa ti crea sicuramente problemi.
int ricerca(int a[], int dim, int n, int pos = 0)
{
//prima condizione di arresto
if(pos>=dim)
{
return -1;
}
//seconda condizione di arresto
if(a[pos]%n==0)
{
return pos;
}
//gestione del passo di ricorsione generico
return ricerca(a, dim, n, pos+1);
}
Scomponendo sempre la scrittura in:
- if condizione di arresto con il return immediato
- gestione del passo di ricorsione generico
si ottiene la divisione di cui ti parlavo all'inizio e non ti incasinerai mai più con gli if else delle condizioni di arresto.
Anche se questo caso è semplice, per generalizzare, per la gestione del passo di ricorsione generico tu sai che puoi avere in mano:
- valore dei parametri attuali della funzione
- valori ritornati delle ricorsioni
Ad esempio: trovare l'ultimo elemento del vettore dispari (nota: bisogna obbligatoriamente eseguire la ricorsione dal primo elemento):
(0) Condizione di arresto: sono arrivato in fondo al vettore
(N) Condizione di ricorsione generica:
(N.1) - valore ritornato dalla ricorsione: posso avere in mano l'indice dell'elemento successivo al corrente che è dispari
(N.2) - parametri attuali della funzione: posso conoscere se l'elemento attuale è dispari
Il codice viene da solo:
int ricerca(int *a, int dim, int i = 0)
{
//(0)
if(i >= dim)
return -1;
//(N)
int res1 = ricerca(a, dim, i + 1); //(N.1)
int res2 = -1;
if(a[i] % 2) //(N.2)
res2 = i;
//se un elemento successivo è dispari il valore è diverso da -1
if(res1 > 0)
return res1;
//altrimenti ritorno res2;
return res2;
}
Questo in prima analisi, dopo si può renderlo più compatto:
int ricerca(int *a, int dim, int i = 0)
{
if(i >= dim)
return -1;
int res1 = ricerca(a, dim, i + 1); //(N.1)
if(res1 > 0)
return res1;
if(a[i] % 2)
return i;
return -1;
}
O ancora più compatto:
int ricerca(int *a, int dim, int i = 0)
{
if(i >= dim)
return -1;
int res1 = ricerca(a, dim, i + 1);
return (res1 > 0 || ! a[i] % i) ? res1 : i;
}
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.