[C] Funzioni ricorsive

[System32]

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 (

Perfavore, Entra oppure Registrati per vedere i Link!

) 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 :

Perfavore, Entra oppure Registrati per vedere i codici!

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 :

Perfavore, Entra oppure Registrati per vedere i codici!

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.

Spero abbiate capito, alla prossima.