Newsgroup: it.comp.lang.c
Titolo: Funzioni ricorsive...

...cosa sono ?
Grazie e ciao a tutti
Mauro              
mailto:
mg...@polbox.com

 ...cosa sono ?
  Funzioni che richiamano se stesse. Prova ad implementare l'algoritmo
per il calcolo del fattoriale. ;)
	Alla prossima,
		Marco

...cosa sono ?
Funzioni che richiamano se stesse.
Sono molto utili in diversi contesti, specialmente per la gestione di
determinate strutture dati (vedi alberi binari, liste, ecc...).
Un esempio di utilizzo di funzioni ricorsive e' quello di gestione di
una lista :
#include <stdio.h>
#include <stdlib.h>
typedef struct item_tag {
                           int x ;
                           struct item_tag * next ;
                        } item ;
typedef item * item_p ;
void inserisci ( item_p * radice, int x )
{
     if ( NULL == *radice )
     {
        *radice = malloc ( sizeof ( item ) ) ;
        (*radice)->next = NULL ;
        (*radice)->x = x ;
     }
     else inserisci ( &(*radice)->next, x ) ; 
     /* la funzione applica se stessa al prossimo elemento */
}
void scrivi ( item_p radice )
{
     if ( radice != NULL )
     {
        printf ( "%2d -> ", radice->x ) ;
        scrivi ( radice->next ) ;
/* anche in questo caso si adotta il medesimo meccanismo per il
prossimo elemento */
     }
     else printf ("NULL\n" ) ;
}
int main()
{
    item_p mia_lista = NULL ;
    inserisci ( &mia_lista, 5 ) ;
    inserisci ( &mia_lista, -3 ) ;
    inserisci ( &mia_lista, 2 ) ;
    inserisci ( &mia_lista, 1 ) ;
    scrivi ( mia_lista ) ;
    return 0 ;
}


ICQ #34602650


~~~~~~~~~~~~~~~~~
MAINARDI Gianfranco
Burago di Molgora (MI)
Italia
Email : 
main...@rete039.it
ICQ# number : 31334916
~~~~~~~~~~~~~~~~~

 pericolose in quanto enormi divoratrici di stack ?
Sicuramente. Però ci sono alcuni problemi che possono essere risolti
molto semplicemente ed elegantemente in modo ricorsivo e in quei casi
sarebbe un vero peccato non utilizzare questa tecnica.
EMG

 pericolose in quanto enormi divoratrici di stack ?
Molto raramente una funzione ricorsiva non può essere sostituita
con un ciclo while() o simile, il quale è in sensibilmente più
veloce (specialmente su macchine RISC) e spreca meno memoria.
D'altra parte, in alcuni casi la funzione ricorsiva è di grande
aiuto, e se utilizzate con moderazione, credo diventi uno stru-
mento insostituibile per la soluzione di alcuni problemi.
Ovviamente, se il codice è difettoso, inefficiente o mal progettato,
le funzioni ricorsive sono in grado di fare piantare un programma
su qualsiasi macchina, ma facendone un utilizzo accorto, non vedo
quel grande pericolo.
Personalmente, evito come la peste questo tipo di funzioni,
dato che quando è il caso di utilizzare il debugger non è
sempre facile tenere traccia del codice o procedere passo-passo.
Aldo.


pericolose in quanto enormi divoratrici di stack ?
Dipende, non e' detto.
Spesso implementare una elaborazione semplice per via ricorsiva e'
senz'altro meno efficiente in termini di consumo di memoria che non
implementarla in modo sequenziale.
Un esempio tipico e' il calcolo del fattoriale.
E' senz'altro meglio implementarlo per via ciclica che non ricorsiva,
sebbene questo calcolo si presti bene al secondo approccio.
In ogni caso, ci sono determinate situazioni in cui la ricorsivita' si
rende addirittura indispensabile, ad esempio per la gestione di alberi
binari.
Ci sono casi, poi, in cui e' presumibile che il consumo di memoria si
mantenga entro certi limiti.
Una situazione del genere e' quella di funzioni risolutrici di
espressioni matematiche che utilizzino un algoritmo di discesa
ricorsiva.
Oppure di funzioni che stampino a video la struttura delle directory
del disco.
In generale, comunque, e' vero che le funzioni ricorsive sono grosse
divoratrici di stack, ma spesso e' anche perche' non si riesce ad
ottimizzare il passaggio di parametri alla funzione e l'utilizzo delle
variabili automatiche.

 sarebbe un vero peccato non utilizzare questa tecnica.
Una cosa interessante da notare e` il feature di alcuni linguaggi,
come scheme e lisp: 'tail recursion'.  Ossia, se la chiamata alla
funzione e` l'ultima istruzione nella funzione, il linguaggio lo
tratta come caso speciale, e non continua ad estendere lo stack.  Per
esempio:
(define (foo x)
  (display x)
  (newline)
  (foo (+ x 1)))
(foo 1)
Che sarebbe, in C:
foo(int x)
{
	printf("%d\n", x);	
	foo(x++);
}
int main()
{
	foo(1);
}
Pero`, l'esempio in scheme puo` continuare senza diventare sempre piu`
grosso, mentre quello in C diventa sempre piu` grande perche` mangia
piu` stack...
Infatti, col tail recursion, non c'e` neanche bisogno dei looping
structures tradizionali, come while, for, ecc.
Ciao,
-- 
David N. Welton, Web Engineer, Linuxcare, Inc.
415.354.4878
 tel, 
415.701.7457
 fax
dwe...@linuxcare.com
, 
http://www.linuxcare.com/
Linuxcare. At the center of Linux.




per il calcolo del fattoriale. ;)
Problema...non capisco niente di matematica :D
Ciao
Mauro              
mailto:
mg...@polbox.com

si applicano?
Gli algoritmi a discesa ricorsiva che caratterizzano un certo tipo di
parser di espressioni matematiche sono tali da analizzare
un'espressione matematica in via ricorsiva, sino a giungere agli
elementi base della stessa (detti "terminali" o token) per elaborarli
e risalire.
In questo modo si riesce a trattare piuttosto facilmente una
grammatica piuttosto complessa.
Ho inserito un programma nella libreria di sorgenti, che illustra
l'utilizzo di un parser a discesa ricorsiva.
Ovviamente l'applicazione di questa tecnica per lo sviluppo di un
compilatore porterebbe inevitabilmente ad un overflow dello stack, in
quanto si sa che la grammatica di un linguaggio e' molto piu'
dettagliata che non quella di un'espressione matematica, ma in
quest'ultimo caso va bene.

Problema...non capisco niente di matematica :D
unsigned long fact ( unsigned long x )
/* versione non ricorsiva */
{
         unsigned long f = 1L ;
         for ( ; x ; f *= x-- ) ;
         return f ;
}
unsigned long rfact ( unsigned long x )
/* versione ricorsiva */
{
         return ( x == 0L ) ? 1L : x * rfact ( x - 1L ) ;
}

 Le variabili locali alle funzioni.
Questa definizione non č esatta. Ad esempio le variabili locali statiche
sono locali ma non automatiche.
EMG



Hai pienamente ragione, e' stata una dimenticanza.
Difatti basta considerare il seguente programma :
#include <stdio.h>
void conta()
{
     static int counter ;
     printf("%d\n", ++counter);
}
int main()
{
    int i ;
    for ( i = 0 ; i < 10 ; i++ )
        conta() ;
}
In realta' per variabili automatiche bisogna intendere quelle la cui
natura risponde per l'appunto a questa automaticita', ovvero quelle
che hanno un "lifetime" corrispondente a quello del corpo di
istruzioni della funzione a cui appartengono.
Le variabili "static" non rispondono, per definizione, a questo
canone.

 quest'ultimo caso va bene.
Vediamo se ho capito bene: nelle espressioni che un compilatore deve
tradurre, possono esserci sottoespressioni più o meno lunghe e contorte (e
ci metto la mano sul fuoco...), che ovviamente non possono essere trattate
con un parser a discesa ricorsiva perchè bisognerebbe memorizzare troppi
dati in una pila delle ricorsioni. E' giusto? Semanticamente, cos'è un
parser?
grazie per l'attenzione

Semanticamente, cos'è un parser?
Un risolutore di espressioni scritte in un linguaggio, secondo una
certa grammatica.

 pericolose in quanto enormi divoratrici di stack ?
Usare la ricorsività può essere l'unica soluzione al problema specifico.
In genere lo stack overflow si ha quando "perdi il controllo" del codice
o quando commetti un errore di progettazione. Ovviamente se intendi
usare una funzione in modo ricorsivo fai anche in maniera di usare meno
stack possibile (poco spazio alle variabili locali, ad esempio).


void main ()
errore :
int main()

al massimo ti becchi un bel warning
Esageriamo pure, invece.
Quante altre volte bisogna ripeterlo che e' scorretto scrivere 
void main() ?
Affrettiamoci a scrivere le FAQ !
Dalle FAQ di comp.lang.c, per la n-esima volta :
1.25b:	What's the right declaration for main()?
	Is void main() correct?
A:	See questions 11.12a to 11.15.  (But no, it's not correct.)
11.14:	I believe that declaring void main() can't fail, since I'm
	calling exit() instead of returning, and anyway my operating
	system ignores a program's exit/return status.
A:	It doesn't matter whether main() returns or not, or whether
	anyone looks at the status; the problem is that when main() is
	misdeclared, its caller (the runtime startup code) may not
even
	be able to *call* it correctly (due to the potential clash of
	calling conventions; see question 11.12b).
	It has been reported that programs using void main() and
	compiled using BC++ 4.5 can crash.  Some compilers (including
	DEC C V4.1 and gcc with certain warnings enabled) will
complain
	about void main().
	Your operating system may ignore the exit status, and
	void main() may work for you, but it is not portable and not
	correct.

pericolose in quanto enormi divoratrici di stack ?
La soluzione ricorsiva e molto più elegante ed ordinata; aumenta
notevolmente la leggibilità del codice.
Però in alcuni casi può notevolmente appesantire la complessità di
calcolo se usato in modo impreciso.
Prova a calcolare il 40-simo numero di Fibonacci con un algoritmo
ricorsivo, non finirà praticamente mai !!!
Provo a sciverlo, non è detto che sia giusto !!
#include <stdio.h>
fib (int n)
{
if (n==1) return 0;
if (n==2) return 1;
return (fib(n-1) + fib (n-2));
}
void main ()
{
printf("\n%d\n",fib(40));
}
Questo algoritmo ha complessità C(n)=2 + C(n-1) + C(n-2), che se non
erro (vado ad occhio) è quasi n^3.
Comunque sia, provare per credere !!
Joyce
ICQ 10607234
Per una pera, una pera cazzo...
Per affrontare questa lunga giornata dura !

 int main()
Non esageriamo...
al massimo ti becchi un bel warning
Ciro

 Sulla mia macchina (P133) ci mette 43 secondi.
Sulla mia (PII400)ci mette circa 35 secondi in modalita' debug e 10 sec. 
in modalita' "definitiva"(relaese)ovvero ottimizzato.
Caro Andrea io nenache mi ci voglio  metetre a dsicutere con te ;-)
Pero' main() puo' essere dichiarata come void.Infatti main() ritorna un 
intero al processo chiamante(di solito il s.o.)la cui restituzione e' 
l'equivalente di una chiamata ad exit()(con l'eccezione di un eventuale 
chiamata ad atexit()).
Se invece main() non restituisce alcun valore,il valore di ritorno sara' 
non definito.La maggior parte dei compilatori C restituira' 
automaticamente uno zero,ma e' bene non farvi affidamento per ragioni di 
trasporatibilita'.Nel caso di main()senza valori di ritorno(e anche di 
altre funzioni non dichiarate esplicitamente void)la maggior parte dei 
compiler emettono un warning(
p.e.il
 mio)quindi basta dichiararla come 
void.
Io spesso uso
void main(){
...
...
exit(0);
}
oppure:
int main(){
...
....
if(..) return 0;
else return -1;
}
Ciao!

 Pero' main() puo' essere dichiarata come void.
Non in C/C++.
EMG

int main(){
E' meglio se impari ad usare solo quest'ultimo.

 void main() e' errato e ti spiego anche il perche'.
Basta pensare a come ci si comporta con le altre funzioni. Una volta
dichiarate in un certo modo sarebbe assurdo utilizzarle con parametri di
tipo diverso o considerare diverso il tipo restituito. Ebbene, la main()
è dichiarata implicitamente come
int main( void );
oppure come
int main( int argc, char **argv );
Qualsiasi altro utilizzo è non solo errato ma anche illogico.
EMG

 E' meglio se impari ad usare solo quest'ultimo.
Io veramente so usare bene quell'ultimo :-)
Sol oche nei mini-mini prog ho cominciato a usare void main()
forse più per piacere che per formalita'(infatti è informale:)
e devo dire che finora non ho mai avuto problemi.Anche i cazzilli che
ho smerciato come freeware finora non mi hanno dato riscontri che dicano 
il contrario.Magari poi li hanno cestinati:-(
Cmq leggero' le f.a.q.A tale proprosito voglio dire che mi dispiace di 
non poter essere d'aiuto nel tradurre le 
f.a.q.in
 italiano perche'la mia 
conoscenza dell'inglese e' mediocre.
Non dimenticate di avvisare quando sono pronte!
Ciao!

conoscenza dell'inglese e' mediocre.
E' un motivo di piu' per spingerci ad affrettare il lavoro.
Io ho forzato la traduzione dall' inglese proprio perche' so che molte
persone non conoscono questa lingua e non e' giusto precluderne la
lettura.

 porting e mai mi capitera',credo...
In realtà basterebbe cambiare complilatore, magari anche una versione
diversa dello stesso, per avere potenzialmente problemi.
EMG

 lettura.
Anche se penso che oggi sia anacronistico pensare di vivere senza
conoscere un minimo di inglese, specie per un programmatore.
EMG

 lettura.
Anche per questo e soprattutto per questo ti ammiro.Odio certe forme di 
"razzismo" che precludono a molte persone  in gamba e volenterose 
l'informazione.Sono stato breve,ma sicuramente ci siamo capiti ;-)  
Ciao e grazie!

 diversa dello stesso, per avere potenzialmente problemi.
Attualmente ne uso due uno per Win 9x e uno per Dos e finora e' andato 
tutto bene.Inoltre quello per Dos e' il vecchio Borland C++ del 1991.
Cmq ho riscoperto int main() :-)
-- 
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-
Che la FoRzA sia con Te...
http://surf.to/CyberZ
http://members.xoom.com/_CyberZ_/
http://members.xoom.com/Neuronix/
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_

conoscere un minimo di inglese, specie per un programmatore.
Purtroppo quel "minimo" di inglese che ci vuole per leggere una faq e'
lo stesso che ci vuole per leggere un articolo in inglese.
Non credo che chi conosca il "minimo" per programmare, sappia anche
leggere un documento tecnico.
A questo punto bisognerebbe prendersela col sistema scolastico.