[C] divide et impera ricorsivo

[gila75]

Allora
punto 1: Credo che il mio dive et impera in fondo sia sbagliato, ci ho riflettuto dopo.
Si può fare iterativo, ma non come ho fatto io...ci penserò più avanti.
@M_A_W: tutte le ragioni del mondo hai, ma sto seguendo un libro, di un autore che pure tu apprezzi, ora non ricordo il nome.
Ma qualche post fa lo hai "lodato" pure tu.
Suddetto libro martella sulla ricorsione, alberi, il problema dello zaino, torri di hanoi, problema del righello ecc..
Ora: io che devo fare??? Secondo te posso ricondurre a iterativo tutto ciò che trovo? NO: sia come tempo che come
conoscenze mie.
M_A_W, parliamoci chiaro, non è che iniziando da zero a 40 anni potrò mai ambire a diventare programmatore dell'anno
Sto solo seguendo un testo...e sembra un buon testo. E li si parla di ricorsione. Almeno la vorrei padroneggiare e arrivare a capire, come te,
che in taluni casi si può sostituire.
Ma scusa, tu come lo sai che è lenta, inutile in alcuni casi ecc ? Con che criterio stabilisci?
Semplice perchè la conosci a fondo

[M_A_W_ 1968]

Ma scusa, tu come lo sai che è lenta, inutile in alcuni casi ecc ? Con che criterio stabilisci?

Semplicissimo: come in ogni altro caso di complessità computazionale e analisi prestazionale, basta contare.

Sommando i tempi di esecuzion medi delle istruzioni in linguaggio macchina generate da una function call in linguaggio C (e in qualsiasi altro linguaggio imperativo con convenzioni standard basate su stack, che siano C-alike, Pascal o una qualsiasi combinazione lineare di codesti metodi vecchi come il cucco) si ottiene un costo notevole perché coinvolge come minimo la creazione di uno stack frame e una serie di salvataggi + ripristini di contesto. Moltiplicando questi costi fissi per la quantità spropositata di chiamate generata da una qualsiasi ricorsione, si ottiene un risultato netto: usare codesta tecnica è praticamente sempre una pessima idea nei linguaggi imperativi tradizionali. Inoltre abbiamo a più riprese chiarito che le eccezioni a codesta regola stanno principalmente nella manipolazione di alberi, foreste e strutture dati avanzate assimilabili (i.e. directories) e nel calcolo di talune funzioni intrinsecamente ricorsive ma particolarmente ostiche, alla Ackermann. Infine, in taluni linguaggi davvero esotici (a partire dai funzionali puri) la ricorsione sostituisce in toto l'iterazione, punto e basta, ma con delle premesse intrinseche sul costo di function call del tutto opposte rispetto a quelle di C, Pascal e compagnia bella. Tutte questioni delle quali probabilmente sentirai parlare qui per la prima e ultima volta.

Quanto agli aspetti teorici più importanti, ci sono interi capitoli di testi di algoritmica dedicati unicamente alle tecniche di eliminazione della ricorsione, in particolare per la tail recursion che è in assoluto il caso più trattabile (anche in automatico, in molti linguaggi evoluti). Dal punto di vista semantico, ricorsione e iterazione sono semplicemente la medesima cosa. Ma come l'uso e abuso di funzioni deprecate da dieci o vent'anni, da scanf() e gets() a fprintf(), anche lo scivolone verso l'abuso della ricorsione ad ogni costo con linguaggi strutturalmente inadeguati sembra caratterizzare una certa didattica.

[gila75]

Che dire M_A_W? Secondo te ho argomentazioni valide? No
Chi "vince" Gila Vs M_A_W? Scontato.
Non so, ho speso...mi pare 50 euro per un manuale...mi costa 2 o 3 settimane per cercare di capire un capitolo...ma si evince che non serve
a nulla.
Sempre più deluso sono.
Inutile proseguire...non metto risolto perchè di fatto non lo è...ma concludo qui il 3d.
P.S.: non c'è polemica o risentimento MAW, solo prendo atto. Sicuramente hai ragione, ma sono confuso e come detto sopra deluso.
Ai tempi qualcuno mi aveva detto che col C era una pazzia, che studi come un matto, ma a conti fatti non concludi nulla.
Non gli volevo credere...ma ahimè...

[Claudio_F]

C:
Da un certo punto di vista lavorare in C è come lavorare in Assembly, ci si deve far carico di una quantità enorme di dettagli che non fanno strettamente parte del dominio del problema da trattare (malloc, sintassi dei puntatori ecc). Chi usa il C lo fa a ragion veduta perchè gli serve il massimo dell'ottimizzazione (tempo di esecuzione o allocazione memoria) o perché ne ha così tanta esperienza che non perde più di tanto tempo a scrivere in questo linguaggio. Ma trattare strutture dati o problemi complessi ha un grande costo in termini di fatica e tempo di sviluppo.
Personalmente quando vedo le decine di righe piene di costanti, dichiarazioni, sintassi, parentesi che servono solo al compilatore e non a risolvere il problema (esattamente come occuparsi di registri e indirizzi di memoria in Assembly) mi passa ogni voglia di approfondire, l'enorme tempo speso, ma soprattutto la mia memoria non più di ventenne , non mi porterebbero ad una reale capacità di produrre rapidamente qualcosa più complesso di un esempio didattico.


Algoritmi:
Le cose che stai affrontando adesso non riguardano più l'apprendimento stretto delle basi del linguaggio, ma algoritmi, strutture dati, e implementazione in C di queste cose. Algoritmi che potrebbero essere benissimo studiati in qualsiasi altro linguaggio imperativo, o addirittura solo in pseudolinguaggio, o in altri casi anche solo matematicamente (es: le espressioni booleane). Ma l'argomento sarebbe ancora più vasto, in C ad esempio non ci sono le classi...


Ricorsione:
Ritengo che ogni cosa (compreso anche ogni linguaggio), indipendentemente dall'applicazione pratica finale, sia un ottimo esercizio per il cervello, e che serva ad ampliare le conoscenze sui numerosi modi possibili per raggiungere un risultato o strutturare un procedimento. Ad esempio Hanoi ho aspettato almeno 25 anni prima di affrontarla, finché mi hanno regalato una Hanoi di legno a 7 dischi (127 mosse se non si sbaglia) e ho voluto replicarla su PC. Serve a qualcosa nella pratica risolvere Hanoi? No, se non a imparare a ragionare in un certo modo

[M_A_W_ 1968]

Ai tempi qualcuno mi aveva detto che col C era una pazzia, che studi come un matto, ma a conti fatti non concludi nulla.
Non gli volevo credere...ma ahimè...

Non devi scoraggiarti. Ci sono decine di linguaggi di alto livello, vicini al dominio dei problemi, di semplice apprendimento, che con una comprensione anche parziale di sintassi e funzionalità ti mettono comunque in grado di giocherellare con la programmazione, senza troppe pretese. Python, Ruby, magari anche Tcl o Icon o Lua se vogliamo andare un po' sull'esotico, ma sempre de noantri, stile Freggene Anzio Nettuno e zone limitrofe (la stagione è proprio quella giusta per i passaggi televisivi dei vari film balneari in bianco e nero con Aldo Fabrizi, la sora Lella e Ave Ninchi)...

La programmazione in linguaggio C, pur essendo un passaggio didattico-applicativo praticamente obbligato per ragioni storiche (doppiamente nel mondo Unix), non è certo la Via Regia per chi voglia semplicemente dilettarsi. Ci sono alternative di ogni genere, per i più vari livelli di utilizzo e preparazione.

[gila75]

Morale della favola: per hobby e da zero il C non è indicato.
Bello arrivare a questa conclusione dopo qualche anno...ma iniziare con altro non me ne vale la pena.
grazie Claudio e M_A_W

[Claudio_F]

per hobby e da zero il C non è indicato

Per hobby ha relativamente poca importanza, è la condizione migliore, non ci sono vincoli di tempo né progetti da portare obbligatoriamente a termine... anche se è comprensibile lo scoramento del non vedere mai la riva... ma in questo campo non si può pensare di conoscere tutto neppure lavorandoci tutto il giorno per decenni. Di fatto le cose che ho trovato troppo difficili le ho sempre skippate, salvo tornarci su se/quando mi servivano. Dopo aver avuto la sensazione di essere arrivato al capolinea con vari dialetti BASIC Pascal Delphi ho anche abbandonato quasi completamente per 6 anni, prima di essere "recuperato" da Python... finalmente un linguaggio al passo con i tempi adatto anche a noi vecchietti

Avere visto liste collegate, puntatori, allocazione della memoria (per non parlare di rudimenti Assembly) permette tra l'altro di avere una visione di insieme di come funzionano le cose in un modo che nessuno di quelli che nascono da zero e continuano solo con linguaggi HLL potrà mai avere. Inoltre non esiste "il" linguaggio unico per fare tutto, ma tanti ambiti applicativi per i quali risulta più vantaggioso se non obbligatorio usarne uno (ad esempio C su Arduino).

Questa immagine mostra i quattro filoni principali (hanno dimenticato Python sotto Java):

Se si tralascia la programmazione logica e quella funzionale, più specifiche per certi problemi, direi che esplorare qualcosa della riga in basso potrebbe essere molto interessante, la semantica e il livello di astrazione permesse dalle istruzioni di un linguaggio ad oggetti sono tutt'altra cosa rispetto alla relativa "povertà" dei linguaggi della prima riga.

[gila75]

Capisco Claudio.
Ora, non vorrei andare fuori tema, quindi cerco di essere breve.
Mi piacerebbe molto spaziare col java il c++ ecc... Ma quando e come? Dove lo trovo il tempo?
Al di la del fatto che fare più cose fatte male non mi va molto.
Sono scoraggiamenti che mi vengono,poi mi passano...e poi ritornano.
La programmazione, rispetto per esempio ai microcontroller (a mio modo di vedere) da molte meno soddisfazioni nell'immediatezza.
Studi,studi ma di concreto fai nulla, se non cose didattiche. Magari fatte bene, comunque non facili, ma pur sempre didattiche.
Con i micro, fai cose concrete e interessanti.
Ho capito benissimo il discorso di M_A_W sulla ricorsione. In effetti impegnare\esaurire lo statck, non credo sia saggio.
Non so se il quick sort in gcc è implementato ricorsivamente, ma supponiamo di si, con array molto grossi si esaurisca lo stack.
Però vorrei anche fargli cercare di capire che il manuale, tratta molti algoritmi, appunto si grafi alberi ecc..in modo ricorsivo.
Quindi al momento io non sono in grado di trasformarli in iterativi.
Io sto solo cercando di pensare anche in altri modi, meno intuitivi, però almeno di capirli.
Mi pare di aver letto che la risoluzione delle torri di Hanoi in modo iterativo, non sia poi così una passeggiata.
Il libro tratta anche il problema dello zaino e tanti problemi logico\matematici che voi sicuramente conoscerete meglio di me.
Per il C che dire? è difficile, o meglio è facile se si scrivono porcherie (anche funzionanti), difficile se si cerca di fare le cose fatte bene.
Non sono stato breve, mi scuserete.
Magari non concluderò mai nulla, ma la cosa mi appassiona e credo fermamente che comunque sia utile come allenamento mentale.
Pazienza se non sarò mai uno Stallman Forse ci dovevo pensare dopo la terza media piuttosto che studiare da odontotecnico (mai
fregato una mazza )
Tornando in tema però: il programma del divide et impera del primo post, si può dire che sia una linea guida del divide et impera?

[vbextreme]

stai studiando il linguaggio più difficile su tali architetture!
Hai 4/5/6 parole con cui puoi creare "il nuovo mondo", ovvio che rimani spaesato.
FREGATENE! trova uno scopo, basta con lo studio approfondito, crea una tua aaplicazione.
Poi oggi crei una "creatura" domani la evolvi in un "mostro", e magari riesci pure a litigare con maw aahhhahahhha..........che bello! quando riuscivo a tirargli fuori qualche chicca!!! peccato non abbia piu tempo come lui.....

[gila75]

FREGATENE! trova uno scopo, basta con lo studio approfondito, crea una tua aaplicazione.

In che senso Vb? Sto studiando problemi fondamentali, che sicuramente tu conoscerai già. Quelle però sono generali, concetti, non strettamente legate
al C.
Una mia applicazione: qualcosa ho fatto, e l'ho pure postato, il labirinto, il riconoscitore toni dtmf, rudimentali filtri con fft.
Ma nessuno se li è filati
Non è studio approfondito a mio avviso, solo concetti fondamentali. Scommetto che tu alberi, ricorsione ecc... te li mangi, sbaglio?
Comunque adesso, cerco di tornare in tema, sono abbondantemente OT

[Claudio_F]

Tornando in tema però: il programma del divide et impera del primo post, si può dire che sia una linea guida del divide et impera?

Del divide si, dell'impera non molto, nel senso che in questo specifico caso (ricerca del numero maggiore in un array non ordinato) dal divide et impera non si ottiene alcun miglioramento rispetto ad una semplice scansione lineare, anzi, a causa della complessità aggiuntiva + chiamate ricorsive le prestazioni crollano.

Diverso è il caso di un sort dove il tempo richiesto cresce esponenzialmente con il numero di elementi, in questo caso sortare "a pezzi" riduce drasticamente il tempo totale (ed è quello che fa il quick sort).

[vbextreme]

Io generalmente studio le cose che mi servono.
ad esempio i grafi li ho solo letti ma non li ho mai usati e quindi mai studiati realmente.
Per farti un'altro esempio sul k&r c'è un capitolo che parla della memoria dinamica, l'ho letto un paio di volte ma l'ho studiato solo qualche mese fa perché mi serviva(il libro l'ho da anni....).

Quindi fatti i tuoi programmi e quando non sai fare una cosa te la studi, ovvio questo non è il migliore metodo però da innumerevoli soddisfazioni, tanto poi hai tutto il tempo per migliorarlo.

[gila75]

Del divide si, dell'impera non molto,

Si in quel caso è vero, divide soltanto

Io generalmente studio le cose che mi servono.
ad esempio i grafi li ho solo letti ma non li ho mai usati e quindi mai studiati realmente.
Per farti un'altro esempio sul k&r c'è un capitolo che parla della memoria dinamica, l'ho letto un paio di volte ma l'ho studiato solo qualche mese fa perché mi serviva(il libro l'ho da anni....).

Quindi fatti i tuoi programmi e quando non sai fare una cosa te la studi, ovvio questo non è il migliore metodo però da innumerevoli soddisfazioni, tanto poi hai tutto il tempo per migliorarlo.

Vero anche quello. Bhà...sono davvero confuso.
Va bhè dai, io ci provo ad andare avanti. In fondo è un hobby, non ho tempi di consegna come in un lavoro

[gila75]

Diciamo che prima del divide et impera secondo me andrebbe vista la ricerca binaria, in cui si incontra la stessa procedura di suddivisione ma senza ricorsione e analizzando semplicemente sottolinsiemi sempre più piccoli scartando il resto

@Claudio intendi questa vero?

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100



int ricercaBinariaNonRicorsiva(int lista[], int n, int x)
 {
    int p, u, m,dimezzamenti;
    p = 0;
    dimezzamenti=0;
    u = n - 1; 
    printf ("u %d\n",u); // per debug
    if (u < 0)
        return -1; 
    while(p <= u) {
        m = (p + u) / 2;
        printf ("m %d\n",m); //per debug
            if(lista[m] == x) 
            {
                printf("fatti %d diemzzamenti\n", dimezzamenti);
                return m; // valore x trovato alla posizione m
            }
        if(lista[m] < x)
        {
            p = m + 1;
            printf ("P %d\n",p);// per debug
            dimezzamenti++;
           
        }
        else
        {
            u = m - 1;
            printf ("U %d\n",u);// per debug
            dimezzamenti++;
            
        }
    }
    // se il programma arriva a questo punto vuol dire che 
    // il valore x non è presente in lista, ma se ci fosse
    // dovrebbe trovarsi alla posizione p (nota che qui p > u)
    return -1;
 }
   
   

int main(void)
{
    int array[N];
    int x=8;
    int i;

    for (i=0; i<N; i++)
    {    
        array[i]=i;
        printf("%d ",array[i]);
    }
    printf("\n\n");
    
    if (ricercaBinariaNonRicorsiva(array,N, x)==x)
        puts("trovato! ");
    else
        puts("non presente");
    return 0;
}

Mi sono confuso. Nel mio manuale viene dopo, ma quella iterativa l'ho già incontrata.
Chissà se bsearc() in gcc è implementata come ricorsiono o iterativa..bhò

[spider-net]

Claudio intendi questa vero?

Sì, quella è la versione iterativa.

Mi sono confuso. Nel mio manuale viene dopo, ma quella iterativa l'ho già incontrata.
Chissà se bsearc() in gcc è implementata come ricorsiono o iterativa..bhò

E' stata implementata in modo iterativo (la trovi qua)

[gila75]

Grazie @spider
suppongo che anche qsort sia stata implementata iterativamente, pur essendo di natura ricorsiva.

[spider-net]

Grazie @spider
suppongo che anche qsort sia stata implementata iterativamente, pur essendo di natura ricorsiva.

Supponi bene.
Comunque non ti abbattere gila. La ricorsione è un buon strumento "didattico", ma come ha detto MAW difficilmente la userai al di fuori della programmazione funzionale (Haskell, Scheme, ...) o della manipolazione di grafi, o di altre problematiche specifiche. A meno che tu non decida di approfondire questi aspetti.

Personalmente ho notato che la ricorsione ricorre spesso in ambito accademico (frequento un corso di laurea in informatica), però viene insegnato anche che tutto ciò che è possibile fare ricorsivamente si riesce anche a fare in modo iterativo. La conversione è molto più immediata se si tratta di ricorsione di coda (tail recursion); l'esempio più semplice e più trattato è di solito la ricerca binaria.

[gila75]

però viene insegnato anche che tutto ciò che è possibile fare ricorsivamente si riesce anche a fare in modo iterativo.

Si, è vero, ma non è sempre così facile.
Per esempio la ricerca del massimo in un array, con il "divide" in modo iterativa, non è così semplice.
Anzi a tal proposito se qualcuno ha il codice e lo posta, me lo studierei volentieri

[ienaplinsky]

Ciao Gila devi simulare uno stack con le chiamate per seguire la ricorsione, io ho provato così non è perfetto però fa il suo dovere

Codice: Seleziona tutto

#include <stdio.h>

#define N 6

typedef struct elem {
	int l;
	int r;
 } Elem;
 
int max(int a[], int l, int r);
Elem pop(Elem *stack, int *index);
void push(Elem *stack, int *index, int l, int r);
 
 int main(void) {
	 int array[N]={100000,20002,0,9999874,5005,88};
	 printf("il massimo dell array e': %d", max(array, 0, N));
 }
 
 int max(int a[], int l, int r) {
	Elem stack[50], tmp;
	int index = -1;
	int max = -1, maxTmp = -1;
	push(stack, &index, l, r);
	while(index != -1) {
		tmp = pop(stack, &index);
		if(tmp.l == tmp.r) {
			if(tmp.l == N) {
				maxTmp = a[tmp.l - 1];
			}
			else {
				maxTmp = a[tmp.l];
			}
		}
		else {
			int m = (tmp.l + tmp.r) / 2;
			push(stack, &index, tmp.l, m);
			push(stack, &index, m + 1, tmp.r);
		}
		if(maxTmp > max) {
			max = maxTmp;
		}
	}
	return max;
 }
 
 Elem pop(Elem *stack, int *index) {
	return stack[(*index)--];
 }
 
 void push(Elem *stack, int *index, int l, int r) {
	stack[++(*index)].l = l;
	stack[*index].r = r;
 }

[gila75]

Grazie Iena. Come supponevo però, "aggiustare" un problema che di propria natura è ricorsivo a iterativo, complica parecchio il codice.
Qui ci si deve appoggiare ad uno stack, non quello di sistema (passami il termine), ma uno creato da noi per poter tener traccia dei massimi "parziali".
Non ho ancora studiato bene il codice, appena posso lo faccio.
Ho notato però un bug: se inseriamo tutti numeri negativi nell'array, il risultato è sempre -1.
Va bhè...a quello ci si pensa poi. M'interessava sapere la strda guida, e tu mi hai detto dello stack. Quella è la cosa importante.
Grazie