Newsgroup: it.comp.lang.c
Titolo: Rieccomi qua :)

Sono arrivato a pagina 86 del K&R seconda edizione e mi si chiede di 
scrivere una funzione ricorsiva reverse(s) che mi faccia l'inverso di 
una stringa. Per non generare discussioni premetto che:
1) sono un autodidatta
2) è il mio primo libro di C
3) tutto ciò che so è compreso nelle 85 pagine precedenti, quindi niente 
puntatori e argomenti successivi :)
4) non importa se l'uso della funzione ricorsiva è efficiente o meno
Dunque, tutto quello che sono riuscito a fare è questa roba qua:
# include <stdio.h>
void reverse (char []);
int main ()
{
   char s[100];
   int i=0;
   while ((s[i++]=getchar()) != EOF)
      ;
   s[i-1]='\0';
      reverse(s);
}
void reverse (char t[] )
{
   static int h=0;
   if (t[h++] != '\0')
       reverse (t);
   putchar (t[--h]);
}
il programmino funziona, ci son stato diverse ore a formularlo e mi ha 
aiutato a capire alcuni concetti che mi erano sfuggiti. A naso non mi 
sembra di aver usato la funzione ricorsiva nella sua potenzialità, mi 
sento come se avessi adoperato un "trucchetto" per ottenere un ciclo al 
contrario. Immagino che ci siano, per questo esercizio, implementazioni 
migliori. Me ne potete suggerire qualcuna?
grazie
-- 
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 ° Toccalenuvole °
         Linux "Slackware" Registered User #341092
 
http://www.toccalenuvole.splinder.com/
   C'ero soltanto. C'ero. Intorno mi cadeva la neve.
				  (K. Issa)
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Questa è la mia versione. La funzione era ricorsiv sicuramente anche se, 
secondo me, la ricorsione era un pò nascosta da quella variabile static.
Se posso avanzare un'ipotesi, ci hai messo tanto tempo proprio perchè 
hai dovuto elaborare il trucchetto di dichiarare la variabile static.
Piuttosto, non capisco perchè, in entrambe le versioni stampa sia la 
scritta al contrario, sia quella normale. Non capisco proprio perchè!
Comunque non è un problema della funzione, piuttosto forse è legato 
all'utilizzo di getc e putc.
Probabilmente non conosco abbastanza bene il comportamento di getc e 
putc (generalmente utilizzo scanf e prinf).
# include <stdio.h>
void reverse (char t[], int h);
int main ()
{
   char s[100];
   int i=0;
   while ((s[i++]=getchar()) !='\n')
      ;
   s[i-1]='\0';
      reverse(s, 0);		// la prima chiamata è leggermente modificata
E' qui (o forse dopo in uscita) che stampa la stringa dritta!!! perchè???
   return 0;
}
void reverse (char t[], int h)
{
   /* static int h=0;
   Secondo me questa variabile static nasconde un pò il senso alla 
ricorsione
   penso tu l'abbia messa perchè pensavi alla versione iterativa 
dell'algoritmo
   Ho modificato il codice in modo da dare un senso più esplicito ad h. 
Infatti puoi vederlo
   come un parametro della funzione che non viene più chiamata sul 
vettore tutto intero
   ma solo su una sua parte quella che parte dall'indice h e arriva al 
tappo.
   Ho modificato anche leggermente il caso base e la chiamata ricorsiva per
   adattarle meglio al mio modo di vedere le cose (devo mettere meno 
incrementi e decrementi),
   nulla vieta che tu possa trovare più semplice vederle in qualche 
altra maniera.
   Con i puntatori sarebbe stata più semplice secondo me :)
   */
   if (t[h] != '\0')		// controlla se la "stringa" non è vuota
       reverse (t, h+1);		// scrive al contrario quella che parte dal 
carattere successivo
							// attenzione che l'incremento deve essere un pre-incremento per 
forza!
 
   putchar (t[h]);		// stampa il carattere corrente
}

 }
Non so bene le regole del gioco, ma penso che utilizzare una variabile 
statica non sia valido se vuoi un codice ricorsivo...
Io farei:
void reverse (char *t) {
  if (*t) reverse(t+1);
  putchar(*t);
}
E.

 
Nono è che sono proprio stanco! speriamo solo quello!
Comunque in bocca al lupo.
Ciao,
Giuseppe

 }
Beh, bello, perň, le regole del gioco erano niente puntatori che non li 
ha fatti ancora... rispettiamo chi ha voglia di imparare!
Ciao,
Giuseppe

 Dunque, tutto quello che sono riuscito a fare è questa roba qua:
Allora, come dice ?manu*, la variabile static è solo un trucchetto. Non
vale. Il fatto che tu ne faccia uso mostra che non hai compreso bene
aspetto cruciale di tutto l'esercizio: ossia che è proprio la ricorsione
che ti deve permettere di mantenere uno stato tra una chiamata e l'altra,
non una variabile globale. (Per inciso, visto che sei principiante, impara
subito che le variabili globali non si devono usare. Mai.)
?manu* ti ha risolto l'esercizio usando i puntatori, che tu non vuoi
(giustamente) usare. Ma il puntatore di ?manu* serve per identificare una
posizione nell'array, e quello lo puoi fare anche passando un intero che
funga da indice. Giusto? Buon lavoro.
Comunque, io sospetto che l'esercizio non ti chieda di stampare l'array al
contrario, ma di copiarlo al contrario in un nuovo array, oppure di
rovesciarlo "sul posto". (In ogni caso, questi sono altri due esercizi che
potresti fare.)
Max

migliori. Me ne potete suggerire qualcuna?
Un'implementazione sicuramente migliore è quella che non fa uso della
ricorsione (che nel caso specifico è come usare un cannone per sparare
alle formiche):
#include <stdio.h>
#include <stdlib.h>
void reverse(char s[]) {
     size_t len=0;
     while (s[len++]) /* ovviamente se non vuoi usare strlen() */
        ;
     if (--len > 1) {
        size_t i=0, mid=len/2; 
        for (; i<mid; i++) {
           char t = s[i]; 
           s[i] = s[len-i-1];
           s[len-i-1] = t;
        }
     }
}
int main()
{
    char q[] = "andrea";
    char r[] = "andreax";
    char s[] = "ab";    
    char t[] = "a";
    char z[] = "";
 
    printf("start testing...\n");
    printf("reverse of \"%s\" is ", q);
    reverse(q);
    printf("\"%s\"\n", q);
 
    printf("reverse of \"%s\" is ", r);
    reverse(r);
    printf("\"%s\"\n", r);    
 
    printf("reverse of \"%s\" is ", s);
    reverse(s);
    printf("\"%s\"\n", s);    
 
    printf("reverse of \"%s\" is ", t);
    reverse(t);
    printf("\"%s\"\n", t);    
    printf("reverse of \"%s\" is ", z);
    reverse(z);
    printf("\"%s\"\n", z);        
    printf("...end testing.\n");
    return 0;
}

 subito che le variabili globali non si devono usare. Mai.)
Per essere precisi l'OP non ha usato una variabile globale
propriamente detta ma una "static block-scope".
P.S.
Come faresti a fare in modo decente una funzione
di libreria come strtok ? Spero non in modo
ricorsivo, povero stack ...
Come allora ?
--
Giorgio Silvestri
DSP/Embedded/Real Time OS   Software Engineer


Ah! Allora:
void reverse(char t[]) {
	if (t[0]) reverse(t+1);
	putchar(t[0]);
}
E.

Come allora ?
Anche l'uso di una variabile statica, però, non va bene.
La funzione strtok, per esempio, non è thread-safe. Un'implementazione
decente della funzione strtok() (laddove il "decente" implica anche un
uso thread-safe) dovrebbe essere state-less, riempire un dato opaco di
controllo per il chiamante e farselo ripassare ad ogni chiamata.
Esattamente come fa strtok_r(), versione rientrante di strtok().

 
Beh... reverse(t+1)... aritmetica dei puntatori!
Comunque neanch'io ci trovo nulla di particolarmente difficile è solo 
che se lui non li ha manco mai visti non ci capisce proprio nulla.
Ciao,
Giuseppe

 Esattamente come fa strtok_r(), versione rientrante di strtok().
Si parlava di strtok non strtok_r (non standard) e ulteriormente
problematica per il "str" iniziale.


 
Ancora, per farti notare una contraddizione, hai appena detto che la 
ricorsione non è abbastanza efficiente... che vuoi usare i missili?
Rilassati non siamo tutti super esperti del linguaggio, dacci il tempo 
di imparare!
P.S.	evidentemente non hai letto la domanda iniziale, punto 4
 > 4) non importa se l'uso della funzione ricorsiva è efficiente o meno
DEVE FARE UN ESERCIZIO!!!
non mandare i razzi sulla luna!

problematica per il "str" iniziale.
Vedi sopra. Se mi chiedi qual è il modo decente di implementare una
funzione come strtok(), io ti rispondo che è quello in cui strtok_r()
è stata implementata. Che poi strtok_r() non sia standard ISO (è POSIX
difatti), non c'entra nulla, si parla della modalità implementativa di
una determinata funzione.

mai sentito parlare di esercizi didattici?
E tu mai sentito parlare di libertà di espressione? io sono libero di
proporre gli esempi che voglio, se ritengo che siano ugualmente
didattici. Non capisco proprio che cosa tu abbia da obiettare.
Se la smetteste, una buona volta, di prendere a pretesto ogni
messaggio per fare della polemica sterile, fareste un servizio a tutto
il gruppo. Nessuno sta incitando a mandare i missili sulla luna. Se lo
scopo di quell'esercizio è quello di insegnare la ricorsione (non
ricordo che cosa c'è scritto a pagina 86 del K&R), allora ben vengano
le implementazioni migliori richieste, che usano la ricorsione. Io ho
proposto una versione che non usa la ricorsione, che è abbastanza
semplice ed efficiente. Di che capperi ti lamenti?

 è stata implementata.
Non è possibile implementare strtok come strtok_r perchè non hanno la stessa
interfaccia.


 ricordo che cosa c'è scritto a pagina 86 del K&R)
C'è nel post iniziale, io non ce l'ho nemmeno il K&R !
Saluti,
Giuseppe

 interfaccia.
Devo dire che, per quanto valga la mia opinione, questa risposta mi è 
piaciuta molto.

Non richiesto dallo standard. 
Stai ripiegando su questo aspetto, che è del tutto irrilevante. La
caratteristica di essere thread-safe non è qualcosa che va
necessariamente richiesta dallo standard. E' una pratica di buona
programmazione quella di evitare dipendenze da strutture che rendono
*automaticamente* il proprio codice inutilizzabile in certi ambiti.
Poi, non girare la frittata, please: tu hai chiesto come implementare
in modo decente una funzione come strtok(), in risposta a un messaggio
di Max M. sull'uso di una variabile statica e, a questo punto, la tua
domanda è ambigua se rispondi con un "non possibile" a chi ti dice
come andrebbe implementata una funzione che svolge la stessa
operazione di strtok(), però in modo decente. Tu non hai specificato
di dover mantenere la stessa interfaccia di strtok(), hai chiesto come
implementare in modo decente una funzione come quella. Il modo decente
di implementare una funzione come quella - e sono tre - è quello (per
esempio) di strtok_r(). Altrimenti qual è la tua reale domanda: "come
implementeresti una funzione come strtok() che sia pari pari a
strtok()?". La risposta che ti aspetti qual'è? "come strtok()"?.
Anche se si volesse mantenere la stessa interfaccia di strtok() è
possibilissimo implementare la funzione in modo state-less, perché
basterebbe restituire, come puntatore, il punto in cui l'analisi si è
fermata, per poi riaccoglierlo in entrata come parametro alla chiamata
successiva.

piaciuta molto.
Già, le frittate rivoltate sono notoriamente più buone ;-)

libertà!
Le obiezioni devono avere un senso e la tua non ce l'ha. Tu ti esprimi
con dei "mai sentito..?" con dei "missili da lanciare", punti il dito
contro (evidenti solo per te) "contraddizioni", urli dei "DEVE FARE UN
ESERCIZIO!!!". Polemica sterilissima. Anche se non rispondo costruendo
del codice ricorsivo, io sono libero di postare del codice che può
comunque aiutare chi sta imparando.
SMETTETELA DI APPIGLIARVI AD OGNI CAZZATA PER FARE POLEMICA!

necessariamente richiesta dallo standard. 
...da aggiungere (poi) che strtok() esiste da molto prima dello
standard.

possibilissimo implementare la funzione in modo state-less
Mi correggo. Questo non è ovviamente possibile perché non si può avere
la moglie ubriaca e la botte piena: un terzo parametro è ovviamente
necessario.

 alle formiche):
Questa è la tua risposta iniziale. Visto che ti si chiede una 
implementazione migliore per questo esercizio nel quale è esplicitamente 
chiesto di utilizzare la ricorsione, a me sembra che scrivere un codice 
iterativo, sia da considerare un errore.
Come puoi vedere dal mio secondo post, quando noto, da solo o per merito 
di qualcuno che ho preso abbagli madornali, non esito a considerarmi un 
emerito imbecille d'altronde tu mi dai torto per principio.
Saluti,
Giuseppe

 successiva.
?
Di quale parametro parli ? strtok si può chiamare successivamente con
NULL come primo parametro. La semantica deve essere la stessa.


iterativo, sia da considerare un errore.
Io non ho letto che si necessitava esplicitamente di una funzione
ricorsiva e quindi non ho postato una soluzione ricorsiva, né ricordo
che cosa si dica a pag. 86 del K&R. Stante questa ammissione, dubito
che il tuo "Rilassati non siamo tutti super esperti del linguaggio"
sia un modo corretto di segnalare un errore interpretativo.

"Andrea Laforgia" <a.laf...@andrealaforgia.it.invalid> ha scritto nel
messaggio news:l3bel3162v427dev2...@4ax.com...

Soprattutto se non sono rivoltate ...


La semantica DEVE essere la stessa.
ROTFL...???... ma che domanda č?
Ma sopratutto: che risposta ti aspetti?
Ripeto quello che ho scritto nel precedente messaggio: che cosa stai
chiedendo? come implementare strtok() in modo che funzioni esattamente
come strtok()? che risposta ti aspetti?

Soprattutto se non sono rivoltate ...
Hai ragione: sopratutto se la domanda iniziale non ha senso.

"Andrea Laforgia" <a.laf...@andrealaforgia.it.invalid> ha scritto nel
messaggio news:stcel3pvgopk2pbab...@4ax.com...

La risposta era molto facile ...
Occorre il concetto di stato. Realizzato con una "static block-scope".
A qualcosa saranno pure utili. E non importa che si perda
la thread-safeness. Si recupera quando serve. Se non serve
si puň anche fare la versione non safe.


"Andrea Laforgia" <a.laf...@andrealaforgia.it.invalid> ha scritto nel
messaggio news:35del39jlucn4782c...@4ax.com...

Il senso bisogna capirlo.


si può anche fare la versione non safe.
Una funzione di libreria deve prevedere tutti gli usi possibili.
Ti lascio comunque crogiolare nelle tue convinzioni. Chiudo qui la
diatriba ignorando completamente il thread.

 Come allora ?
Beh, 'strtok' è una delle cose più inutili che ci siano nella libreria
standard del C. (Più inutile di strcat.) 
E' non rientrante  "by-design". Infatti hanno presto sentito la necessità di
inventarsi "strtok_r". Quindi non c'è modo di implementarla "decentemente".
Devo però correggere Andrea su un punto. Pur essendo non-rientrante, strtok
può essere comunque resa thread-safe, e so che in certe implementazioni lo
è. (Forse anche in quella GNU.)  In queste implementazioni viene usato un
thread-specific storage per mantenere lo stato. (Analogo trucchetto viene
usato per rendere thread-safe 'errno'.)
Max

 Una funzione di libreria deve prevedere tutti gli usi possibili.
Non necessariamente (esempio ci sono delle limitazioni
nel chiamare funzioni nei signal-handler).
Normalmente sono piů efficienti le versioni non-safe.
Meglio averle entrambe che solo quelle "super".
Fortunatamente lo standard non obbliga certe cose ...


 usato per rendere thread-safe 'errno'.)
Esattamente. E' il senso di quando dico che certe cose si possono
recuperare. Nel senso che a volte vengono fornite 2 versioni.
Thread-safe e non. Entrambe hanno senso secondo me.


 usato per rendere thread-safe 'errno'.)
Perň il problema di strtok non si evidenzia solo nel multi-threading. 
Basta che tra una chiamata e un'altra di strtok vai a chiamare una 
funzione di cui non conosci il codice. In tal caso se anche la funzione 
che hai chiamato utilizza strtok sei nei guai.
E.

 stato.
Aggiungo una cosa: rendere strtok thread-safe serve unicamente a far
funzionare il codice esistente in un contesto multithread. Un TTS č
presumibilmente (molto) meno efficiente di una variabile (static o globale
che sia). In queste condizioni usare deliberatamente strtok ha veramente
poco senso. E infatti non la usa nessuno. E la "deprecano" tutti.
Max

 che hai chiamato utilizza strtok sei nei guai.
Certo. Come si č detto, strtok č una funzione non rientrante e gli
inconvenienti di questo non sono limitati al multithreading. Anzi, al
limite, i problemi con l'esecuzione concorrente possono essere in qualche
modo risolti, ma i problemi classici della "non-rientranza" rimangono.
Max

   Con i puntatori sarebbe stata piů semplice secondo me :)
immagino, ma ci arriverň a breve cosě non vi assillerň piů...almeno sul 
fatto di non saperli :)
-- 
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 ° Toccalenuvole °
         Linux "Slackware" Registered User #341092
 
http://www.toccalenuvole.splinder.com/
   C'ero soltanto. C'ero. Intorno mi cadeva la neve.
				  (K. Issa)
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 che se lui non li ha manco mai visti non ci capisce proprio nulla.
infatti non c'ho capito niente...


 subito che le variabili globali non si devono usare. Mai.)
ok, hai confermato anche tu la mia sensazione...almeno in fatto di 
intuito progredisco :)


 }
questa mi sembra l'implementazione migliore _ANCHE SE_ io il putchar
l'avrei infilato dentro l'if, non ha senso _puttare_ uno 0 sullo
stdin.
Daniele

 stdin.
Hai ragione! E' stata una svista...
E.