Pagina 1 di 2
[C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 19:33
da gila75
Ciao a tutti, sto risolvendo il famoso esercizio dell'allineamento parentesi, come esercitazione con lo stack.
Ho scritto un codice, e tra l'altro colgo l'occasione, se avete voglia, di dirmi se va bene o meno, e se si può migliorare.
A titolo puramente didattico, vorrei scrivere la versione ricorsiva.
La ricorsione l'ho affrontata, ma mai nello specifico.
Non voglio che me la scriviate voi, ma solo consigli e dritte: non conviene per quel caso, oppure si, snellisce tutto ecc.
So che la ricorsione, come detto da un utente, spesso toglie dai guai...esempio apertura di sottocartelle nella lettura/creazione di sottodirectory.
Ma so anche che ci sono pareri (e pareri che pesano (M_A_W) ) che è tendenzialmente contro la ricorsione.
Comunque, mi basterebbe per ora un ok sul codice. L'ho rifatto un paio di volte per via di casi particolari dove veniva scritto espressione ok, quando invece non lo era
Ora sembra esente da bugs.
Magari provate anche voi e se notate errori segnalatemelo per favore
Ecco:
Codice: Seleziona tutto
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 500
int analizza (char input[],char stack[],int top,int len);
void input_char (char str_input[],int n);
void push (char exp,char stack[],int *top);
int pop (char exp,char stack[],int *top);
void push(char exp,char stack[],int *top)
{
(*top)++;
stack[*top]=exp;
}
int pop(char exp,char stack[],int *top)
{
int flag=0;
if (stack[*top]=='(' && exp==')')
{
flag++;
(*top)--;
}
if (stack[*top]=='[' && exp==']')
{
flag++;
(*top)--;
}
if (stack[*top]=='{' && exp=='}')
{
flag++;
(*top)--;
}
return flag;
}
int analizza (char input[],char stack[],int top,int len)
{
int i,res_pop;
for (i=0; i<len; i++)
{
if (input[i]=='(' || input[i]=='[' || input[i]=='{')
{
push(input[i],stack,&top);
}
if (input[i]==')' || input[i]==']' || input[i]=='}')
{
if ( (res_pop=pop(input[i],stack,&top))==0)
return 0;
}
}
return top;
}
void input_char(char str_input[],int n)
{
int len;
fgets(str_input,n,stdin);
len=strlen(str_input);
str_input[len-1]='\0';
}
int main(void)
{
char input[N];
char stack[N]={0};
int top=-1;
int len,res;
puts ("input frase : ");
input_char(input,N);
printf ("Espressione da valutare:%s\n", input);
len=strlen(input);
res=(analizza(input,stack,top,len));
if(res==-1)
{
puts("Espressione regolare");
}
else
{
puts("Espressione non regolare");
}
return 0;
}
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 21:23
da vbextreme
essendo al cellulare non riesco a vedere il codice, la ricorsione è una funzione che richiama se stessa con argomenti diversi.
Perché MAW no gli aggrada?Semplice, essendo un esperto di architetture embedded la ricorsione è un "ciuccia" memoria a "tradimento".
Quando tu ti richiami la funzione devi mettere nello stack la posizione di ritorno alla funzione, lo stack stesso e i parametri, in più devi aggiungere tutte le variabili usate, insomma se su un PC è tollerata perché snellisce il codoce e ne snellisce la comprensione sui sistemi più " piccoli" è inammissibile, perche alle volte lo stack a disposizione per chiamate a sotto funzioni è molto ridotto.
Oltre a questo c'è naturalmente da considerare il "costo" computazionale che richiede la ricorsione.
Va sicuramente imparata, mi è capitato di scrivere un algoritmo ricorsivo e poi in un successivo momento riscritto con altre tecniche, anche qui MAW storcerebbe il naso per il semplice fatto che le cose andrebbero fatte una volta sola e fatte bene, ma io non ne sono ancora in grado e certe volte preferisco tornare sopra al codice per ottimizzarlo avendo però sotto delle solide fondamenta
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 21:41
da gila75
Ciao vb.
Su sitemi ebedded, sono daccordissimo.
Ora non ci gioco più, ma uc a 8bits a stcak ridotto, direi che è improponibile.
Li si ottimizza tutto e ancora di più. Considerando poi che per esempio un pic, va a 8 massimo 20Mhz (serie 16 sono rimasto

)
Ogni spreco diventa esponenziale e la lentezza aumenta.
Anche però su un pc ho notato delle differenze se non erro.
Fare un fattoriale ricorsivo (un po' consistente) e iterativo, mi pare cambiassero i tempi.
Considerando poi che la ricorsione ha un limite di chiamate, date appunto dalla dimensione dello stack stesso.
Comunque, il mio è il classico esecizio delle parentesi:
[[()]] corretto
()( scorretto
Innanzitutto si ti/vi va mi piacerebbe avaere tuoi/vostri consigli o critiche sul codice.
In secondo luogo vorrei trasformarlo (a patto che sia possibile) in ricorsivo.
Sto studiando su ("Algoritmi in c") la ricorsione e vorrei esercitarmi.
Grazie nel caso

Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 21:51
da vbextreme
continuo ad essere sul phone, magari dopo il week+end se mi ricordo...
Il discorso è semplice, se su un micro da 8 bit, magari pure con pochi MHz va piano se non è addirittura impossibile fare, cosa accade su un micro più "grosso"?
Ecco perché se uno parte dai " chippini" poi è avvantaggiato sui "bestioni" che poi dopotutto non sono tali.
Una volta feci un algoritmo per riempire un area delimitata da dei contorni, scriverlo con algoritmo ricorsivo fu una passeggiata ma nonostante avesssi la swap superata una certa risoluzione/grandezza di riempimento collassava tutto.
Alla fine sono passato ad un semplicissimo stack interno che ha triplicato le performance e >>5 la memoria usata.
Se la vedi col senno di poi lo swap non esisterà più e in un certo senso si tornerà indietro alle "amate" ottimizzazioni.
È dunque assolutente necessario conoscere fino all'ultimo dettaglio cosa si può fare e soprattutto come meglio farlo, valutando caso per caso quale algoritmo sia meglio implementare.
Se non li conosci... non puoi scegliere...
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 22:13
da gila75
continuo ad essere sul phone, magari dopo il week+end se mi ricordo...

scusa
certo sapere pregi e difetti di ogni algoritmo è l'ottimo (se si può dire)
Ricordo per esempio che per la scansione delle directory, proprio tu mi avevi consigliato la ricorsione.
Per il fattoriale però mi viene un dubbio: non è più snello e veloce:
Codice: Seleziona tutto
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int fat=12;
int i;
int t=1;
for (i=1; i<fat; i++)
t=t+t*i;
printf ("%d\n",t);
return 0;
}
??
va bhe ne riparleremo se ti va.
Se hai tempo prova a vedere se rilevi bugs nel codice se hai voglia

Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 22:30
da Actarus5
Gila credo che questa versione del fattoriale sia piuttosto ingenua ( naive) e va bene solo quando si tratta di mostrare la differenza con la versione ricorsiva ( che è identica alla definizione sostanzialmente), nel caso in cui tu abbia bisogno di calcolare il fattoriale in un programma ci sono algoritmi più efficienti!
Purtroppo vado di corsa anche io, ma domani guardo anche l'altro codice e lo provo!
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 22:35
da ubuntumate
Beh più veloce sì,in genere le versioni iterative godono di performance migliori.Snello? No.
Codice: Seleziona tutto
int fattoriale(int n)
{
if(n == 1 || n == 0)
{
return 1;
}
else
{
return n*fattoriale(n - 1);
}
}
A sembra più elegante e snella la versione ricorsiva.Mi scuso se ho scritto codice strambo,ma vengo da una full immersion di Python
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 23:15
da vbextreme
@ubuntu potevi sforzarti un po di più...
Codice: Seleziona tutto
unsigned factotum( unsigned v )
{
if ( v < 2 ) return 1;
return v * factotum( v - 1 );
}
python like:
Codice: Seleziona tutto
unsigned factotum(unsigned v){
if ( v < 2 )
return 1;
return v * factotum( v - 1 );}
@Gila come detto in precedenza va valutato caso per caso, se per leggere da HD tutte le directory impieghi 10 secondi poco cambia se il tuo algoritmo impiega 1 o 0,5 secondi.
certo che 10,5s < 11s ma un utente se ne accorge?
discorso diverso se alla fine di una ricerca riparti con quella successiva * 24h * 30g *12m....
Va valutato caso per caso.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: venerdì 29 maggio 2015, 23:40
da Claudio_F
Ricordo per esempio che per la scansione delle directory, proprio tu mi avevi consigliato la ricorsione.
Per il fattoriale però mi viene un dubbio: non è più snello e veloce:
Il fattoriale è un caso particolare, nonostante possa essere descritto in forma ricorsiva si può implementare tramite un semplice contatore e accumulo, e allora si è più veloce e non porta via memoria se non quella richiesta da contatore e accumulatore.
In ogni caso comunque se il procedimento è intrinsecamente ricorsivo, come l'attraversamento del file system o il quick sort, l'implementazione ricorsiva è più "naturale" e compatta.
Non so il caso specifico di vbextreme, ma secondo me usare un array-stack manuale al posto del call-stack della ricorsione non dovrebbe portare a grandi miglioramenti, anzi, bisognerebbe allocare in anticipo tutta la memoria presumibilmente necessaria per il caso peggiore.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: sabato 30 maggio 2015, 1:28
da vbextreme
Non so il caso specifico di vbextreme, ma secondo me usare un array-stack manuale al posto del call-stack della ricorsione non dovrebbe portare a grandi miglioramenti, anzi, bisognerebbe allocare in anticipo tutta la memoria presumibilmente necessaria per il caso peggiore.
Teoricamente parlando, ogni chiamata alla factotum costa:
indirizzo ritorno + indirizzo stack + argomento N + teorico salvataggio dei registri( in questo caso un buon compilatore potrebbe usare un registro unico senza nemmeno "sporcare" lo stack con il passaggio della variabile, magari usando eax ad esempio per l'x86, proprio il registro che si usa per il return.)
In buona sostanza si ha parecchio spreco di memoria.
Il mio caso è abbastanza semplice, se su/giù/SX/dx != mio colore && non ho elaborato colora e reitera.Niente di complicato, ti assicuro che un semplice stack è decisamente più efficiente, usando gli stack hai poi tutta una serie di opzioni in più da aggregarsi.
Prova a pensare di riempire un quadrato 800*600 partendo dal centro, entri in fill() x e y vuoti si?coloro, su è vuoto?si bene richiamo fill() e cosi * 300 volte e poi sei a 0 ora vai a SX? bene altre 400 volte poi giù altre 300 e via a via prima di uscire dall'ultima iterazione ti sarai avvicinato alle 800*600 chiamate.
quanto costano?
800*600=480000 * 8(indirizzo ritorno + indirizzo stack) = 3840000byte = 3750kb = 3.7mb.
Ti sei mangiato la gestione di 3.7 MB senza aver fatto niente, aggiungici un po di contorno e hai fatto tombola.
Unica precisazione gli algoritmi di riempimento sono abbastanza complicati e richiedono parecchie astuzie per ottimizzarle....
Re: [C] da iterativo a ricorsivo aiuto
Inviato: sabato 30 maggio 2015, 13:27
da M_A_W_ 1968
Riguardo al fattoriale, sono note almeno
due dozzine di algoritmi validi, molti dei quali sono
raccolti qui. La versione ricorsiva è semplicemente impresentabile.
Repetita juvant: la ricorsione è
Male con praticamente tutti i linguaggi imperativi e OO di terza e quarta generazione, e con molti altri. Si veda anche
questa discussione.
Questo perché, come già spiegato a più riprese, le convenzioni di chiamata più diffuse (vulgo: C e Pascal) comportano sprechi di memoria e di prestazioni semplicemente inammissibili in un caso ricorsivo, creando un overhead eccessivo legato al numero spropositato di function calls generate a runtime. Quindi se lavorate in C, C++, Python, Ruby, whatever:
dimenticatevi semplicemente che esista. E se non potete farne a meno, siate almeno in grado di quantificare lo slack prestazionale.
Esistono comunque tecniche asseverate di eliminazione della ricorsione, sebbene si abbiano casi di ricorsione multipla decisamente ostici dal punto di vista algoritmico (alberi e foreste, o alcune rarissime funzioni ricorsive) e talora, nel real world, si avalla qualche tradeoff optando per la forma ricorsiva, rinunciando
scientemente a delle prestazioni accettabili pur di non complicare oltre misura il codice e/o allungare i tempi di sviluppo.
Viceversa, in altri contesti la ricorsione (in particolare la tail recursion) è non solo ampiamente accettabile, ma praticamente inevitabile, vedansi linguaggi funzionali come Miranda, Haskell, ML, Scheme e dintorni (Prolog, B-Prolog, eccetera).
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 10:55
da gila75
Grazie ragazzi per le risposte.
Allora, il caso del fattoriale che dicevo, secondo me è più veloce e intuitivo la versione ricorsiva, ma sono pareri.
In altri casi, il ricorsivo toglie parecchio dai guai:
http://forum.ubuntu-it.org/viewtopic.ph ... 9&start=40
ultimo programma. Grazie alla ricorsione non devo tener traccia di nulla e il programma fa quello che deve fare.
@M_A_W:
Sonon confuso, hai una preparazione nel campo enorme, quindi prendo atto di quello che dici, ma sto studiando un libro
di Robert Sedgewick :
http://it.wikipedia.org/wiki/Robert_Sedgewick
Dove dice che la ricorsione è importante per alberi, grafi ecc..
Ora, mi sono documentato su Robert_Sedgewick e non mi sembra sia un cialtrone...ma rimango confuso.
Tu dici: dimenticatevi che esiste la ricorsione, sul libro spinge a imparare...mannaggia!!!
Che faccio ?
Molti algoritmi e problemi, quick sort, torri di Hanoi ecc.. vengono spiegati ricorsivamente. Vero che tutto ciò che è ricorsivo
lo si può fare iterativo e viceversa, ma non sempre la complessità rimane uguale.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 11:06
da Claudio_F
Molti algoritmi e problemi, quick sort, torri di Hanoi ecc.. vengono spiegati ricorsivamente. Vero che tutto ciò che è ricorsivo
lo si può fare iterativo e viceversa, ma non sempre la complessità rimane uguale.
Non vedo il problema, tutto torna utile, dipende se nel caso specifico conta di più risparmiare risorse macchina o tempo uomo / complessità (vale anche per la scelta di un linguaggio).
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 12:16
da gila75
Sicuramente quello.
Però quando un utente con decenni d'esperienza si pronuncia in modo così sfavorevole due domande me le faccio.
Ok, che M_A_W mira a livelli d'ottimizzazione e precisione che io mai potrò affrontare.
Però visto che il tempo è poco e le cose da studiare sono tante, uno (io) rimane perplesso.
Nel mio libro un sacco d'argomenti mirano alla ricorsione...poi vieni a scoprire che è "cattiva" pratica, che fai?
Il mio è solo un esercizio: vorrei trasformare il codice scritto in ricorsivo, in modo da vedere le differenze e poi valutare.
a proposito, nessuno l'ha provato ?
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 12:46
da vbextreme
@MAW ha scritto: sebbene si abbiano casi di ricorsione multipla decisamente ostici dal punto di vista algoritmico (alberi e foreste, o alcune rarissime funzioni ricorsive) e talora, nel real world, si avalla qualche tradeoff optando per la forma ricorsiva
@gila come vedi MAW ha detto che ci sono alcuni casi, come quelli da te esposti, che implementare un metodo iterativo è molto difficile e quindi viene "abbonato" l'uso ricorsivo.
Bisognerebbe sempre optare per un metodo iterativo ma quando proprio non si riesce allora si può usare la ricorsione, quindi bisogna studiarla!
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 12:48
da Claudio_F
poi vieni a scoprire che è "cattiva" pratica, che fai?
Ma non è cattiva in sè (in Prolog se non ricordo male *bisogna* usare la ricorsione) è solo inefficiente dal punto di vista prestazionale. In Python poi, oltre che lenta perché in questo linguaggio le chiamate a funzione sono già lente in sè stesse, è pure limitata a circa mille livelli... quindi ricorsione per modo di dire.
Se intendo bene la tua domanda probabilmente è: "se la ricorsione è così inefficiente, vale la pena perdere tempo a studiare soluzioni ricorsive?"
La risposta secondo me è la stessa di: "se un linguaggio HLL come Python è così inefficiente, vale la pena di perdere tempo a studiarlo?"
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 12:52
da M_A_W_ 1968
Ciò che scrive il buon vecchio Sedgewick è sacrosanto. D'altro canto, è esattamente quanto ho già accennato sopra: alberi e foreste sono i casi più tipici, sebbene non gli unici, nei quali spesso il costo della eliminazione della ricorsione è tale da scoraggiare la schiacciante maggioranza degli implementatori, quale che sia il linguaggio a disposizione.
Inoltre, mi ripeto, ci sono intere famiglie di linguaggi e paradigmi nei quali la ricorsione è intrinseca e quindi obbligatoria, dai funzionali ai dichiarativi, eccetera. Viceversa, è del tutto inadeguata con linguaggi come C e Python.
Dunque, riassumendo: qualche esercizietto di implementazione ricorsiva in linguaggio C non ti farà certo male. Ma devi anche capire che posto occupa la ricorsione nel panorama delle soluzioni a disposizione di un buon programmatore.
Dunque se poi, nel risolvere qualche problema concreto, ti venisse in mente di usare la ricorsione per una soluzione in C, fattene passare la voglia immediatamente. Le probabilità che tu abbia a che fare con foreste di alberi bilanciati o con il calcolo di funzioni stile Ackermann sono pressoché nulle, e in base a ciò in prospettiva le tue effettive necessità di usare la ricorsione in un linguaggio inadeguato come C tendono definitivamente a zero.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 15:40
da gila75
Ciò che scrive il buon vecchio Sedgewick è sacrosanto. D'altro canto, è esattamente quanto ho già accennato sopra: alberi e foreste sono i casi più tipici, sebbene non gli unici, nei quali spesso il costo della eliminazione della ricorsione è tale da scoraggiare la schiacciante maggioranza degli implementatori, quale che sia il linguaggio a disposizione.
ok ho capito.
Grazie e grazie anche a @vb e @Claudio per i consigli.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 21:41
da vaeVictis
Scusate per la brutalità di questo mio intervento, ma vorrei ricevere le notifiche della discussione, che trovo interessante.
Re: [C] da iterativo a ricorsivo aiuto
Inviato: domenica 31 maggio 2015, 21:56
da gila75
Scusate per la brutalità di questo mio intervento, ma vorrei ricevere le notifiche della discussione, che trovo interessante.
in che senso vae? Ti riferisci allo staff?