[C] Progettazione di funzioni ricorsive

[Jecko]

ciao a tutti! Sono uno studente di ingegneria informatica, tra pochi giorni ho un esame di algoritmi e strutture dati piuttosto tosto e ho un problemino con la ricorsione:
nonostante capisca perfettamente gli esercizi già svolti e tutte le varie strutture dati che sono implicitamente correlate alla ricorsione (BST, grafi, heap, ecc...) e le sappia anche sviluppare negli esercizi teorici, quando mi trovo a dover scrivere una funzione ricorsiva per un qualsivoglia programma in C troppo spesso mi ritrovo a fissare il foglio(ebbene si ci fanno fare l'esame su carta...)/monitor come un ebete senza sapere da dove iniziare. La mia richiesta è quindi se qualcuno sia in grado di darmi due dritte generali sul modo di affrontare la progettazione di una funzione ricorsiva dalla condizione di terminazione, al backtrack ecc... grazie e scusate per la domanda generica

[giannola]

i più comuni esempi sono quelli di fibonacci, basta che cerchi su google "fibonacci c", l'algoritmo è semplice, una funzione che restituisce se stessa.

[Perseverance]

Il backtracking è una cosa differente dalla ricorsione. Col backtraking invece di esplorare lo spazio totale delle soluzioni, scarti intelligentemente uno o più sottogruppi di soluzioni che sicuramente non vanno bene. Il "problema delle regine" è un classico esempio.

La ricorsione è la cosa più semplice che possa esistere, in C non la puoi fare ma in C++ si (a quelche sò io). Mandare in ricorsione una funzione è banale, basta richiamarla. Il problema è farla terminare, per questo ci sono le condizioni di STOP.

Le condizioni di STOP vanno valutate in base al problema. Di ogni algoritmo iterativo è possibile scrivere un algoritmo ricorsivo che svolge la stessa funzione (ma non è detto che abbia la stessa complessità).

Come si impara:
Si impara facendo cose semplici, il nostro cervello per natura è abituato a pensare in modo iterativo, il nostro inconscio (e le varie funzioni vitali) in modo ricorsivo. Perciò pensare in modo ricorsivo risulta difficile; devi fare l'idea di ragionare su 1 solo caso (quello ricorsivo che vale poi per tutti), non te ne fregare di cosa succede dopo, tu pensa a quell'unico caso buono.

Prima fase: Individua i casi BASE in cui la tua funzione ricorsiva DEVE fermarsi
Seconda fase: scrivi il codice per IL passo ricorsivo e solo per quello
Terza fase: richiama la funzione facendo in modo che lavori su un insieme sempre più piccolo. In questo modo garantisci che sicuramente cascherà in uno dei casi BASE. Di solito la funzione ricorsiva ha sempre dei parametri che possono essere spesso e volentieri degli indici (come il count del for ad esempio)

Esempio scemo: prendi in input un numero N da tastiera e stampa a video da N=5 a 0 quindi esci:

Funzione sbagliata: mancano i casi BASE in cui si deve fermare
void funzione(int conta) {
  cout << conta << endl;
  funzione (conta-1);
}

int main()
{
  funzione(5)
  return 0
}

Questa funzione sintatticamente è corretta ma non produce il risultato aspettato, xkè non si ferma arrivata a 0 ma continua a -1 -2 -3 ... Se vuoi che si fermi a 0 devi imporre il CASO BASE che non avevo scritto, nel caso base ESCI, cioè dai il comando return. Siccome è VOID non deve ritornare niente quindi accando a return non c'è niente. Il caso base và posizionato all'interno della funzione in modo opportuno e non a casaccio:

Funzione scorretta xkè non printa lo 0, esce prima (esce dopo aver printato 1)!
void funzione(int conta) {
  if(conta==0) return;
  cout << conta << endl;
  funzione (conta-1);
}

Funzione corretta
void funzione(int conta) {
  cout << conta << endl;
  if(conta==0) return;
  funzione (conta-1);
}

Questa cicla all'infinito OK? non essendoci un caso base prima della chiamata
la funzione NON ritornerà mai e quindi NON andrà mai a vedere il codice
di sotto alla chiamata ricorsiva
void funzione(int conta) {
  if(conta==0) return;
  cout << conta << endl;
  funzione (conta-1);

  //Altre istruzioni che non saranno mai eseguite...
  return;
}

Else o no Else ?
Ti troverai sicuramente a chiederti: "metto l'else dopo l'if oppure và bene così?"

Per questo non c'è una regola, ma devi guardare bene che la funzione non si inceppi se lo metti, a volte è superfluo altre volte fà molti danni. Ad esempio se metti un else nella funzione di prima non cambia nulla:

Funzione corretta 2
void funzione(int conta) {
  cout << conta << endl;
  if(conta==0)
     return;
  else
     funzione (conta-1);
}

Mentre in questa combini del casino (voglio sapere se un numero è pari o dispari): Praticamente gli sottraggo 2 finchè non giungo a 0 oppure a 1, se arrivo a 0 allora il num di partenza era pari, altrimenti dispari. Con questo ragionamento un lamer pensa subito di usare l'else, sbagliando giustamente!

Funzione CORRETTA:
void pari_o_dispari(int num)
{
  if(num==0){ cout << "pari"; return;}
  if(num==1){ cout << "dispari"; return; }
  pari_o_dispari(num-2);
}

La seguente è scorretta xkè quell'else significa qualunque numero diverso da 0
e praticamente già alla prima iterazione dice che è dispari ed esce ammeno
che tu non gli passi 0 come parametro.

Funzione NON CORRETTA:
void pari_o_dispari(int num)
{
  if(num==0){
     cout << "pari";
     return;
  }
  else{
     cout << "dispari";
     return;
  }
  pari_o_dispari(num-2);
}

Probabilmente con gli algoritmi sugli alberi il problema dell'else si fà più sentire, di solito non ci vuole, ma bada bene di ragionare e magari fai qualche passo mentale di algoritmo per vedere quelche viene fuori.

[clockover]

Originariamente inviato da Perseverance

La ricorsione è la cosa più semplice che possa esistere, in C non la puoi fare

perchè no scusa

[Jecko]

Intanto grazie mille a tutti delle risposte soprattutto Perseverance che si è prodigato in una lunga spiegazione Purtroppo quello che proprio mi manca è il ragionamento ricorsivo su cose un po' più complicate. Ad esempio vi posto un tema d'esame ke mi ha dato del filo da torcere:

Una azienda di trasporti possiede degli autocarri con portata utile pari a 100 quintali.
Si scriva un programma C che:
• legga da un file (il cui nome `e stato preventivamente acquisito da tastiera) le informazioni relative
ad una generica spedizione, ossia:
– il numero dei colli (prima riga del file);
– per ogni collo, il peso (in quintali); l’informazione relativa a ciascun collo occupa una riga
del file;
• trovi una sistemazione dei colli sugli autocarri, in modo che il numero di autocarri necessario
per la spedizione sia minimo, e per nessun autocarro non sia superata la portata massima; `e
inoltre richiesto che lo sbilanciamento di carico tra i vari autocarri sia minimizzato.
• visualizzi:
– il numero k di autocarri necessario;
– per ogni collo, il numero d’ordine dell’autocarro (tra 0 e k − 1) su cui va caricato;

Di seguito vi riporto il codice della soluzione

int cercaSoluzione ( collo_t *colli , int nColli , int * autocarri , int nAuto , int id , int nOpt)
112 {
113 int i;
114
115 if (id == nColli) {
116 /* trovata una soluzione */
117 if (nOpt ==0 || nAuto <nOpt || verificaSoluzione (colli , nColli , autocarri , nOpt )) {
118 for (i =0; i< nColli ; i ++)
119 colli[i]. autocarro = colli[i]. tmp ;
120 return nAuto;
121 }
122 return nOpt;
123 }
124
125 /* assegna il collo di indice "id " ad un autocarro */
126 for (i=0; i< nAuto; i ++) {
127 if ( autocarri [i] + colli[ id ]. peso <= MAXPESO ) {
128 colli[ id ]. tmp = i;
129 autocarri [i] += colli[id ]. peso;
130 nOpt = cercaSoluzione (colli , nColli , autocarri , nAuto , id +1, nOpt);
131 colli[ id ]. tmp = -1;
132 autocarri [i] -= colli[id ]. peso;
133 }
134 }
135
136 if ( nOpt==0 || nAuto <nOpt) {
137 colli[id ]. tmp = i;
138 autocarri [i] += colli[id ]. peso;
139 nOpt = cercaSoluzione (colli , nColli , autocarri , nAuto+1, id +1, nOpt);
140 colli[id ]. tmp = -1;
141 autocarri [i] -= colli[id ]. peso;
142 }
143
144 return nOpt;
145 }

dove collo_t è questa struct

struct collo {
8 int peso; /* peso del pacco */
9 int autocarro ; /* autocarro a cui e’ assegnato */
10 int tmp ; /* autocarro temporaneo ( per la ricorsione ) */
11 };

ridefinita come ADT in un altro header file. Su questo tema il mio problema è stata proprio la scelta della struttura dati (tra l'altro banale) che ha condizionato il mio ragionamento sulla funzione ricorsiva (una cosa implica l'altra e se sbagli una....). Poi ogni esercizio è un caso a parte, per questo in particolare ad esempio non avevo proprio capito come distribuire i colli tra i vari autocarri mantenendo contemporaneamente il bilanciamento... Non vi posto la mia funzione perchè, semplicemente, non l'ho scritta... Ah comunque in C si possono scrivere funzioni ricorsive, il mio esame è sostanzialmente su quello

[Perseverance]

Allora mi sbagliavo con altri linguaggi di programmazione, non tutti permettono la ricorsione.

Sostanzialmente il problema richiedeva di minimizzare una funzione a più variabili (funzione obiettivo) dato un insieme di vincoli, ricade fra i problemi di "ottimizzazione" (ricerca operativa). Fra gli algoritmi più famosi che svolgono questa cosa (ovviamente i parametri vanno adattati) trovi: Kruskal, Dijkstra, Algoritmo del simplesso. Ok belle parole ma poi non ci si fà niente, xkè nel tuo problema non vè specificato ad esempio l'ingombro, il grafo di nodi con le strade, camion con portata differente, tragitti differenti, flussi forzati...

Il problema dice che "la ditta ha degli autocarri di portata 100 quintali", da ciò io deduco che siano tutti da 100qt, inoltre è implicito che il peso di 1 collo debba essere minore di 100 altrimenti non c'entra sul camion.

In breve quello che devi fare è: prendere i dati di una spedizione in input da file, scrivere il numero di colli, quanto pesano, e su quali autocarri sono montati.
L'algoritmo invece si deve occupare di come sistemare i colli sugli autocarri + deve far in modo che siano bilanciati.

Ora te lo dico sinceramente, non ho voglia di scrivere il programma ma te lo dico a grandi linee com'è venuto in mente a me la soluzione. Questo tipo di problemi fanno parte dal "famoso" gruppo chiamato "Algoritmi Greedy", un esempio celeberrimo è "disposizione di N libri in una cartella" oppure da wikipedia: Il problema "Dai il minor numero di monete di resto utilizzando monete da 100, 10, 1 eurocent" è un problema risolvibile tramite un algoritmo di tipo greedy: ad ogni passo viene controllato il resto ancora da dare e si aggiunge la moneta con valore maggiore possibile. Quindi per dare un resto di 112 eurocent la macchina farà cadere in sequenza una moneta da 100, poi 10, poi 1, e infine ancora 1 eurocent (per un totale di 4 monete).

Soluzione parziale:
...Seguendo la filosofia greedy parto a riempire i camion dal pacco più pesante a quello più leggero controllando ogni volta che non superi le dimensioni di ingombro (nel tuo caso solo il peso in quintali), se le supera vado ad analizzare il pacco successivo e se c'entra ce lo metto. Come prerequisito i colli devono essere in una struttura dati ordinata per peso! In questo modo sei sicuro di riempire correttamente tutti i camion.

Adesso xò c'è da capire cosa si intende per "sbilanciamento del carico", idealmente potrebbe essere la media matematica (il peso medio complessivo) [ (a+b+c+d+e)/5 ] a non dover essere superato oppure ad ammettere un certo margine di errore. Ad esempio se ho 10kg 30kg 5Kg 8Kg 7Kg, riordinandoli ho 5-7-8-10-30=60Kg che in media fà 12Kg. Mettiamo che abbia 2 autocarri significa che il peso di un autocarro non deve superare di più di 12Kg l'altro e che il carico deve essere ripartito entro i 60/2=30Kg.

Seguendo sempre l'algoritmo greedy puoi iniziare a leggere di cima e porti nella condizione di non superare i 30Kg, in questo modo caricherai esattamente 5+7+8+10=30 sul primo carro, e i restanti 30 sul secondo. 30-30=0<12Kg. Termini quando la disposizione sul carro è ottima E quando il delta del peso medio complessivo è rispettato, oppure quando non c'è soluzione che banalmente la vedi facendo un semplice conto: PORTATA TOTALE DEI CAMION >= CARICO COMPLESSIVO DI TUTTI I COLLI ? Se sì c'è soluzione, altrimenti no. Questa la devi verificare subito all'inizio.

E' così semplice, boh, l'ho fatto in 5 minuti probabilmente no, ma testiamolo:
Colli Kg= 1-2-3-50-80-90
Carri 2= 200Kg
Soluzione? 200Kg < 226Kg non esiste soluzione

Colli Kg= 1-2-3-50-80-90
Carri 3= 300Kg
Soluzione? 300Kg > 226Kg esiste una soluzione, troviamola

Peso medio=37
Delta=226/3=75

[Camion1]: 1+2+3+50+stop=56 > 35 m.a <75
[Camion2]: 80+stop=80 >35 m.a >75
[Camion3]: 90+stop=90 >35 m.a >75

I vincoli sono rispettati quindi è una soluzione ottima. E' la migliore? proviamo le altre combinazioni:
[Camion1]: 1+2+3+50+80 = oltre la capacità
[Camion2]: 90 = ok
[Camion3]: ? = e questo che che lo carico?

[Camion1]: 90+1+2+3 = 96 ok
[Camion2]: 80 = ok
[Camion3]: 50 = ok

Questa è un'altra soluzione, migliore o peggiore? confontiamo questa con la precedente soluzione:
Differenza massimo-minimo < 35?
A-> 90-56=34 < 35 OK
B-> 96-50=46 > 35 KO!

Quest'ultima è una soluzione ma peggiore della precedente.
E per induzione (lol) l'algoritmo funziona...(sehh sehh vedremo!)

Così è come l'avrei fatto io, poi è chiaro che sbaglierò sicuramente ehh! Ma intanto ho voluto divertirmi un pochino...

[clockover]

Mi avevi fatto venire il dubbio anche a me poi ho dovuto fare subito una funzione stupida di prova..

[cionci]

Non capisco se la tua difficoltà è nello studiare un algoritmo di risoluzione o nello scriverlo in forma ricorsiva.
Potresti riportare la soluzione in una forma più leggibile, quindi indentata e senza i numeri ad inizio riga ?

[Perseverance]

Cionci, penso che abbia difficoltà a pensare una strategia risolutiva, forse non c'entra nemmeno il problema che sia ricorsiva o meno.

[cionci]

Originariamente inviato da Perseverance

E' così semplice, boh, l'ho fatto in 5 minuti probabilmente no, ma testiamolo:
Colli Kg= 1-2-3-50-80-90
Carri 2= 200Kg
Soluzione? 200Kg < 226Kg non esiste soluzione

Colli Kg= 1-2-3-50-80-90
Carri 3= 300Kg
Soluzione? 300Kg > 226Kg esiste una soluzione, troviamola

Ci sono anche casi in cui la somma dei pesi è minore del carico totale, ma non esiste soluzione ammissibile

Ad esempio:

3 pacchi da 60Kg
1 pacco da 50Kg

3 carri = 300 Kg

[Jecko]

Allora il mio problema è stata proprio la funzione ricorsiva perchè inizialmente stavo utilizzando proprio un algoritmo greedy: avevo calcolato il numero di autocarri necessari facendo ceil(peso_totale/100) arrotondando per eccesso. Dopo averci lavorato un po' però, memore proprio del problema dello zaino da riempire, ho deciso di scartare la soluzione greedy (che come dici tu non deve essere necessariamente ricorsiva, anzi...). Il fatto è che in casi in cui le quantità sono discrete l'approccio greedy non offre soluzione ottima. Se invece avessimo potuto prendere parti frazionarie dei singoli colli allora l'algoritmo sarebbe stato ok. A quel punto mi sono reso conto che la soluzione doveva essere ricorsiva ed esplorare tutto l'albero delle soluzioni, questo però non sono riuscito a capire come realizzarlo. Quella che vi ho postato e che ora vi riscrivo ben indentata (scusate per il copia-incolla molto grezzo di prima... mea culpa) è la soluzione fornita dal prof:

int cercaSoluzione ( collo_t *colli , int nColli , int * autocarri , int Auto , int id , int nOpt)
 {
 int i;

 if (id == nColli)  /* trovata una soluzione */
           {
            if (nOpt ==0 || nAuto <nOpt || verificaSoluzione (colli , nColli , autocarri , nOpt )) 
                   {
                    for (i =0; i< nColli ; i ++)
                    colli[i]. autocarro = colli[i]. tmp ;
                    return nAuto;
                    }
             return nOpt;
          }

 /* assegna il collo di indice "id " ad un autocarro */
     for (i=0; i< nAuto; i ++) 
           {
            if ( autocarri [i] + colli[ id ]. peso <= MAXPESO ) 
                   {
                    colli[ id ]. tmp = i;
                    autocarri [i] += colli[id ]. peso;
                    nOpt = cercaSoluzione (colli , nColli , autocarri , nAuto , id +1, nOpt);
                    colli[ id ]. tmp = -1;
                    autocarri [i] -= colli[id ]. peso;
                    }
           }

      if ( nOpt==0 || nAuto <nOpt) 
             {
              colli[id ]. tmp = i;
              autocarri [i] += colli[id ]. peso;
              nOpt = cercaSoluzione (colli , nColli , autocarri , nAuto+1, id +1, nOpt);
              colli[id ]. tmp = -1;
              autocarri [i] -= colli[id ]. peso;
              }

        return nOpt;
 }

e che ancora non mi è chiarissima... grazie ancora a tutti per l'aiuto

[cionci]

Esplorare tutto l'albero delle soluzioni secondo me può avere senso. Basta cominciare con un numero di autocarri pari a ceil(peso_totale/100), ma in ogni caso non è detto che esista una soluzione ammissibile, come dimostrato sopra.
Devo ancora mettermi a leggere la soluzione del prof...lo guardo un po'...

[khelidan1980]

Originariamente inviato da Perseverance

Allora mi sbagliavo con altri linguaggi di programmazione, non tutti permettono la ricorsione.

la ricorsione è una tecnica, non capisco che centri con il linguaggio, mi ricordo di aver fatto funzioni ricorsive pure in assembly