Ultima modifica:
Salve...mi sono appena iscritto ( http://www.inforge.net/community/presentati-alla-community/256395-salve-new-post.html ) e subito mi trovate qui a postare una "guida" che ho scritto sul Forum - di cui parlo nella presentazione e dal quale me ne sono scappato a gambe levate -. La posto qui perché mi è sembrato di vedere gente seria e pertanto gradirei un vostro parere su quanto leggerete. Mi limito ad incollare la guida, buona lettura :
Salve, oggi volevo parlarvi delle funzioni ricorsive cercando di farvi capire la logica secondo cui esse operano e il perché risultino - nella maggior parte dei casi - più utili rispetto a delle normali funzioni. Prima di parlarvi di funzioni ricorsive è bene che spieghi cos'è una "normale" funzione : ebbene una funzione non ha un significato ben definito, una funzione è un "procedimento" - si suppone matematico/logico - che permette di svolgere determinati compiti con la differenza che la funzione può essere richiamata in qualsiasi parte del programma. Si suppone che la maggior parte - se non tutti - dei programmi per computer sia costituita da funzioni che permettono sì il corretto svolgimento del programma ma che danno anche una certa logica e "semplicità" a quest'ultimo, ecco perchè è bene suddividere il proprio codice in piccole ( per "piccole" si intende non kilometriche ) funzioni, questo modo di strutturare un programma è detto dividi e conquista ( dal latino divide et impera ). A questo punto si può parlare di funzioni ricorsive : una funzione ricorsiva non è altro che una "normale" funzione che all'interno del suo corpo ( il corpo di una funzione è il blocco di istruzioni che essa esegue racchiuso tra parentesi graffe { } ) richiama se stessa. Per capire meglio come essa richiama se stessa è bene che vi faccia capire come lavora una funzione ricorsiva : normalmente quando ci troviamo davanti al computer per scrivere un programma dobbiamo prima ragionare su come potremo scrivere il programma ( quindi dovremo pensare anche a quali funzioni scrivere, cosa queste funzioni dovranno fare e via dicendo ) e quindi cercare di "costruire una logica di programmazione". Quest'insieme di ragionamenti per il computer si chiamano problemi; come tutti sapete - spero - il computer è ignorante, conosce talmente tante sequenze di 0 e 1 che è inabilitato a conoscere il resto, e allora chi glielo insegna il resto ? La risposta è semplice : noi, come ? - direte voi -, attraverso la scrittura del codice ( che si presume segua una logica ). Cos'ha tutto questo a che fare con le funzioni e specialmente con le funzioni ricorsive ? Dovreste averlo capito : le funzioni "normali" e le funzioni ricorsive non fanno altro che spezzare - logicamente, non praticamente - le istruzioni che voi avete fornito ( e che quindi volete che la funzione esegua ) in tanti piccoli "problemi"; affinché però questi problemi possano essere risolti c'è bisogno che la funzione abbia un "esempio base" da cui partire in modo da poter proseguire con la sua esecuzione. Esistono 2 tipi di problemi : problemi semplici - altro non sono che gli "esempi di base" da cui parte la funzione - e problemi "complicati"; i problemi semplici saranno risolti immediatamente dalla funzione mentre i problemi complicati non saranno risolti ( non sto parlando di "risoluzione a livello di tempo" sto parlando di "risoluzione a livello di soluzione", ciò significa che una funzione ricorsiva, prima che risolva il problema più complicato, deve avere un punto da cui partire : ovvero l'esempio di base. Adesso che avete capito - si spera - come "ragiona" una funzione ricorsiva possiamo passare ad un esempio : il classico esempio che viene fornito di funzione ricorsiva è il calcolo del fattoriale ( Fattoriale ) di un numero e anch'io in questo thread utilizzerò questo esempio facendo la distinzione tra il calcolo del fattoriale senza utilizzare una funziona e quello con una funzione ricorsiva :
Calcolo del fattoriale senza nessuna funzione :
Penso non ci sia niente da dire a riguardo, il codice e i commenti parlano da sé; al massimo vi spiego la logica del ciclo for : facciamo finta che il valore immesso dall'utente sia 5 i valori delle variabili - al primo ciclo - saranno quindi questi :
- valore variabile number = 5
- valore variabile contatore = 5
- valore variabile fattoriale = fattoriale ( 1 ) * contatore ( 5 ) quindi : 5 * 1 = 5
- nuovo valore variabile contatore = 4 ( contatore-- )
al secondo ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 4
- valore variabile fattoriale = fattoriale ( adesso vale 5 ) * contatore ( 4 ) quindi : 5 * 4 = 20
- nuovo valore variabile contatore = 3 ( contatore-- )
al terzo ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 3
- valore variabile fattoriale = fattoriale ( adesso vale 20 ) * contatore ( 3 ) quindi : 20 * 6 = 60
- nuovo valore variabile contatore = 2 ( contatore-- )
al quarto ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 2
- valore variabile fattoriale = fattoriale ( adesso vale 60 ) * contatore ( 2 ) quindi : 60 * 2 = 120
- nuovo valore variabile contatore = 1 ( contatore-- )
al quinto ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 1
- valore variabile fattoriale = fattoriale ( adesso vale 120 ) * contatore ( 1 ) quindi : 120 * 1 = 120
- nuovo valore variabile contatore = 0 ( esce quindi dal ciclo perchè nel for viene "violata" la condizione contatore >= 1 )
Calcolo del fattoriale con una funzione ricorsiva :
al primo ciclo :
1! = 1
al secondo ciclo :
2! = 2 * 1 = 2
al terzo ciclo :
3! = 3 * 2 = 6
al quarto ciclo :
4! = 4 * 6 = 24
al quinto ciclo :
5! = 5 * 24 = 120
Importante : Volevo fare un piccolo discorso riguardo il tipo di ritorno utilizzato nella funzione Fattoriale : quando si scrive long nome_variabile è come se si scrivesse long int, lo standard del C specifica che una variabile di tipo long int debba essere immagazzinata in almeno 4 byte e di conseguenza che possa contenere un valore grande quanto +2147483647. La funzione ricorsiva per il calcolo del fattoriale - mano a mano che i numeri dei quali calcolare il fattoriale aumentano - restituisce numeri sempre più grandi ( ovviamente ) ragion per cui il fattoriale sarà calcolabile solo fino ad un certo numero. Per "ovviare" a questo scomodo problema sarebbero necessari dei valori float o double.
int0x80
Salve, oggi volevo parlarvi delle funzioni ricorsive cercando di farvi capire la logica secondo cui esse operano e il perché risultino - nella maggior parte dei casi - più utili rispetto a delle normali funzioni. Prima di parlarvi di funzioni ricorsive è bene che spieghi cos'è una "normale" funzione : ebbene una funzione non ha un significato ben definito, una funzione è un "procedimento" - si suppone matematico/logico - che permette di svolgere determinati compiti con la differenza che la funzione può essere richiamata in qualsiasi parte del programma. Si suppone che la maggior parte - se non tutti - dei programmi per computer sia costituita da funzioni che permettono sì il corretto svolgimento del programma ma che danno anche una certa logica e "semplicità" a quest'ultimo, ecco perchè è bene suddividere il proprio codice in piccole ( per "piccole" si intende non kilometriche ) funzioni, questo modo di strutturare un programma è detto dividi e conquista ( dal latino divide et impera ). A questo punto si può parlare di funzioni ricorsive : una funzione ricorsiva non è altro che una "normale" funzione che all'interno del suo corpo ( il corpo di una funzione è il blocco di istruzioni che essa esegue racchiuso tra parentesi graffe { } ) richiama se stessa. Per capire meglio come essa richiama se stessa è bene che vi faccia capire come lavora una funzione ricorsiva : normalmente quando ci troviamo davanti al computer per scrivere un programma dobbiamo prima ragionare su come potremo scrivere il programma ( quindi dovremo pensare anche a quali funzioni scrivere, cosa queste funzioni dovranno fare e via dicendo ) e quindi cercare di "costruire una logica di programmazione". Quest'insieme di ragionamenti per il computer si chiamano problemi; come tutti sapete - spero - il computer è ignorante, conosce talmente tante sequenze di 0 e 1 che è inabilitato a conoscere il resto, e allora chi glielo insegna il resto ? La risposta è semplice : noi, come ? - direte voi -, attraverso la scrittura del codice ( che si presume segua una logica ). Cos'ha tutto questo a che fare con le funzioni e specialmente con le funzioni ricorsive ? Dovreste averlo capito : le funzioni "normali" e le funzioni ricorsive non fanno altro che spezzare - logicamente, non praticamente - le istruzioni che voi avete fornito ( e che quindi volete che la funzione esegua ) in tanti piccoli "problemi"; affinché però questi problemi possano essere risolti c'è bisogno che la funzione abbia un "esempio base" da cui partire in modo da poter proseguire con la sua esecuzione. Esistono 2 tipi di problemi : problemi semplici - altro non sono che gli "esempi di base" da cui parte la funzione - e problemi "complicati"; i problemi semplici saranno risolti immediatamente dalla funzione mentre i problemi complicati non saranno risolti ( non sto parlando di "risoluzione a livello di tempo" sto parlando di "risoluzione a livello di soluzione", ciò significa che una funzione ricorsiva, prima che risolva il problema più complicato, deve avere un punto da cui partire : ovvero l'esempio di base. Adesso che avete capito - si spera - come "ragiona" una funzione ricorsiva possiamo passare ad un esempio : il classico esempio che viene fornito di funzione ricorsiva è il calcolo del fattoriale ( Fattoriale ) di un numero e anch'io in questo thread utilizzerò questo esempio facendo la distinzione tra il calcolo del fattoriale senza utilizzare una funziona e quello con una funzione ricorsiva :
Calcolo del fattoriale senza nessuna funzione :
Codice:
/* fattoriale.c */
#include "stdafx.h" /* header standard di Visual Studio, voi se usate altri IDE includete stdio.h */
#include <conio.h> /* header per la funzione getch(); portabile su linux */
int main() /* il programma inizia dalla funzione main() */
{
int numero; /* numero del quale calcolare il fattoriale */
int fattoriale = 1; /* il fattoriale è dato da n * (n - 1) * (n - 2) * ... * 1 per cui assegno a "fattoriale" il valore 1 */
printf("Inserisci il numero del quale calcolare il fattoriale : "); /* stampo a schermo la stringa tra virgolette */
scanf("%d", &numero); /* faccio scegliere il numero all'utente */
for(int contatore = numero; contatore >= 1; contatore--) /* inizio ciclo for */
fattoriale *= contatore; /* fine ciclo for - calcolo del fattoriale ( che equivale a scrivere fattoriale = fattoriale * contatore ) */
printf("%d! = %d", numero, fattoriale); /* stampo il fattoriale a schermo */
getch(); /* verrà chiesto all'utente di premere un tasto per chiudere il programma */
return 0;
} /* fine funzione main() - fine programma */Penso non ci sia niente da dire a riguardo, il codice e i commenti parlano da sé; al massimo vi spiego la logica del ciclo for : facciamo finta che il valore immesso dall'utente sia 5 i valori delle variabili - al primo ciclo - saranno quindi questi :
- valore variabile number = 5
- valore variabile contatore = 5
- valore variabile fattoriale = fattoriale ( 1 ) * contatore ( 5 ) quindi : 5 * 1 = 5
- nuovo valore variabile contatore = 4 ( contatore-- )
al secondo ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 4
- valore variabile fattoriale = fattoriale ( adesso vale 5 ) * contatore ( 4 ) quindi : 5 * 4 = 20
- nuovo valore variabile contatore = 3 ( contatore-- )
al terzo ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 3
- valore variabile fattoriale = fattoriale ( adesso vale 20 ) * contatore ( 3 ) quindi : 20 * 6 = 60
- nuovo valore variabile contatore = 2 ( contatore-- )
al quarto ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 2
- valore variabile fattoriale = fattoriale ( adesso vale 60 ) * contatore ( 2 ) quindi : 60 * 2 = 120
- nuovo valore variabile contatore = 1 ( contatore-- )
al quinto ciclo :
- valore variabile number = sempre 5
- valore variabile contatore = 1
- valore variabile fattoriale = fattoriale ( adesso vale 120 ) * contatore ( 1 ) quindi : 120 * 1 = 120
- nuovo valore variabile contatore = 0 ( esce quindi dal ciclo perchè nel for viene "violata" la condizione contatore >= 1 )
Calcolo del fattoriale con una funzione ricorsiva :
Codice:
/* fattoriale.c */
#include "stdafx.h" /* header standard di Visual Studio, voi se usate altri IDE includete stdio.h */
#include <conio.h> /* header per la funzione getch(); portabile su linux */
long Fattoriale(long numero); /* prototipo della funzione Fattoriale */
int main() /* il programma inizia dalla funzione main() */
{
int numero; /* numero del quale calcolare il fattoriale */
printf("Scrivi il numero del quale calcolare il fattoriale : "); /* stampo a schermo la stringa tra virgolette */
scanf("%ld", &numero); /* faccio scegliere il numero all'utente */
printf("%d! = %ld", numero, Fattoriale(numero)); /* stampo a schermo il risultato */
getch(); /* verrà chiesto all'utente di premere un tasto per chiudere il programma */
return 0;
} /* fine funzione main() - fine programma */
long Fattoriale(long numero) /* funzione vera e propria */
{ /* inizio funzione Fattoriale */
if( numero <= 1 ) /* inizio istruzione if - verifico che il numero inserito dall'utente sia <= 1, se lo è restituisce 1 in quanto fattoriale di 1 = 1 */
return 1;
else /* altrimenti restituisco la moltiplicazione tra il numero scelto e il fattoriale del numero - 1 */
return ( numero * Fattoriale(numero - 1)); /* restituisco il fattoriale */
} /* fine funzione Fattoriale */al primo ciclo :
1! = 1
al secondo ciclo :
2! = 2 * 1 = 2
al terzo ciclo :
3! = 3 * 2 = 6
al quarto ciclo :
4! = 4 * 6 = 24
al quinto ciclo :
5! = 5 * 24 = 120
Importante : Volevo fare un piccolo discorso riguardo il tipo di ritorno utilizzato nella funzione Fattoriale : quando si scrive long nome_variabile è come se si scrivesse long int, lo standard del C specifica che una variabile di tipo long int debba essere immagazzinata in almeno 4 byte e di conseguenza che possa contenere un valore grande quanto +2147483647. La funzione ricorsiva per il calcolo del fattoriale - mano a mano che i numeri dei quali calcolare il fattoriale aumentano - restituisce numeri sempre più grandi ( ovviamente ) ragion per cui il fattoriale sarà calcolabile solo fino ad un certo numero. Per "ovviare" a questo scomodo problema sarebbero necessari dei valori float o double.
int0x80
