[C++] Problema ricorsione

[Cory]

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.

[cionci]

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.

[cionci]

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!]

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
}

[cionci]

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!]

Originariamente inviato da Antonio23

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

[Cory]

Originariamente inviato da cionci

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"

[cionci]

Parti da questo esercizio, scrivimi le condizioni di arresto, poi ti insegno anche qualche trucchetto, questo esercizio si presta bene

[Cory]

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?

[cionci]

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.

[Cory]

Originariamente inviato da cionci

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...

[cionci]

Cory, ripeto scrivi le condizioni di arresto della ricorsione PRIMA ed in questa forma:

if(condizione)
return;

[Cory]

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..

[cionci]

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.

[Cory]

uff non ci capisco un cazzo

[cionci]

Originariamente inviato da Cory

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.

[Cory]

Originariamente inviato da cionci

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

[cionci]

pos non ti serve, non ce lo devi mettere perché ritorni già -1, togli pos dal prototipo della funzione.

[Cory]

if(a[i]%n==0) return i;
if(i==dim-1) return -1;

[cionci]

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.