[C++] Comprendere e applicare la ricorsione

[Johnny_Firpo]

Salve, è un po che posto esercizi sulla ricorsione sul forum, ho capito pure che cos'è è come funziona, ma trovo difficoltà ad essere rapido sulla risoluzione dei problemi ricorsivi.
Siccome a breve ho l'esame di fondamenti di informatica, volevo sapere se conoscete online qualche guida fatta bene!
Avete qualche metodo per risolvere rapidamente gli esercizi?
Lo so che puo sembrare sciocca come domanda, ma a volte c'è una chiave per risolvere le cose, ed io non ho capito


grazie

[stevemaster]

Guide? alla fine il metodo è quello, devi essere bravo tu a mettere le giuste condizioni nella funzione per applicarla.
L'unico metodo per imparare è fare tanta, tanta, tanta pratica... so che è brutale, ma è così....
Dovresti provare a usare il lisp (come ho fatto io al secondo anno) che si basa tutto sulla ricorsione... lì sì che ti fai le ossa!

[Johnny_Firpo]

Grazie

[Johnny_Firpo]

ecco, sono andato di nuovo in pappa

devo fare una funzione boleana ricorsiva, che vale vare se l'intero c è contenuto almeno una volta in un'array

bool verifica(int a[],int n, int c)
{

    if (a[0]==1)  return true;  // come via di fuga non va bene nenanche if(n==1)


 if(a[n]==c)
 return verifica(a,n--,c);

 else return false;

    }


int main()
{
int n=5;

int aa[]={1,9,6,7,8};

if(verifica(aa,n,6)) cout<<"si c'è"<<'\n';
if(!verifica(aa,n,6)) cout<<"no, non c'è"<<'\n';

return 0;
}

ecco il mio problema, è che non riesco a trovare la via di fuga.
Quale potrebbe essere una via di fuga?
Grazie mille

[Stoicenko]

perchè sbagli la logica.. devi vedere se un elemento è contenuto in un array no?

quindi, o lo scorri in avanti o lo scorri all'indietro.. decidi tu..

bool verifica(int a[], int pos, int numero, int dim)
{
	if(pos >= dim) return false; //scorrendo in avanti ho superato il limite..
	else
	{
		if(a[pos] == numero) return true; //l'elemento c'è...
		else
		{
			return verifica(a, ++pos, numero, dim); //cerco nella pos successiva
		}
	}
	
}

int main()
{
	int n=5;

	int aa[]={1,9,6,7,8};

	if(verifica(aa, 0, 6, n)) cout<<"si c'è"<<'\n';
	else cout<<"no, non c'è"<<'\n';

	int x =0;
	cin>>x;

	return 0;
}

[Johnny_Firpo]

è, ma io era la via di fuga che non trovavo, perchè cmq io verificavo ogni elemento dell'array, quindi non c'è una via di fuga per la mia soluzione?

grazie per la risposta

[Stoicenko]

la tua soluzione non mi sembra corretta.. soprattutto perchè quando trovi che il numero è presente continui la ricorsione.. e ciò è sbagliato.. per logica la tua via di fuga (chiamata "caso base" che è più corretto e logico) dovrebbe essere n < 0

[Johnny_Firpo]

Infatti proprio questo ti volevo chiedere:

Guardando l'esempio del contare quante volte un intero compare in un array:

#include <iostream>
#include <cstdlib>



using namespace std;



int occorrenza(int a[],int n, int c)
{

if(n=0) return 0;


if(a[n]==c)  // se non si trova l'uguaglianza, comunque non riparte!
return occorrenza(a,n--,c)+1;


    }


int main()
{
int n=7;

int cc=6;

int aa[]={1,9,6,7,6,8,6};

cout<<"il "<<cc<<" è contenuto "<<occorrenza(aa,n,cc);


return 0;
}

é vero che come ho scritto io se non trova l'intero alla posizione n, non riparte la ricorsione?

ovvero, mi trovo ad un certo punto che non vale ver l'if, ma in questo modo non va avanti la ricorsione giusto?

in questo caso, va bene la via di fuga ma non so portare avanti le chiamate ricorsive

[Johnny_Firpo]

prca miseria, l'esercizio di ricorsione all'esame mi vale 8 punti come devo fare...

[Stoicenko]

quell'esercizio è ovviamente sbagliato..

#include <iostream>
#include <cstdlib>

using namespace std;

int occorrenza(int a[],int n, int c)
{

     if(n == 0) return 0; //attento che ci vuole il doppio = 


     if(a[n] == c)  // se non si trova l'uguaglianza, comunque non riparte!
     {  
        return occorrenza(a, n--, c) + 1;
     }
     else
     {
       return occorrenza(a,n--,c); //basta non aggiungere 1
     }

}


int main()
{
     int n=7;

     int cc=6;

     int aa[]={1,9,6,7,6,8,6};

     cout<<"il "<<cc<<" è contenuto "<<occorrenza(aa,n,cc);

     return 0;
}