[C++] Problema ricorsione

[cionci]

Guarda che l'avevi già scritto prima il codice corretto per questa parte.

[~FullSyst3m~]

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

[cionci]

Originariamente inviato da ~FullSyst3m~

Sinceramente la spiegazione mi è sembrata un pochettino confusionaria

Ah sì, questo è poco ma sicuro 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~]

Originariamente inviato da cionci

Ah sì, questo è poco ma sicuro 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.

[Cory]

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.

[cionci]

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.

[Cory]

scusa, ma tu come lo faresti?? perchè più che quello che ho scritto sopra non saprei che diavolo fare..

[cionci]

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;
}