come funziona la ricorsione (esempio fattoriale)

ciao a tutti!!!
oggi parliamo degli algoritmi ricorsivi.

wikipedia ci suggerisce questa definizione:
Viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati.

In pratica un'algoritmo ricorsivo usa se stesso per eseguire le stesse operazioni su un numero minore di dati.

Un famoso esempio per la spiegazione degli algoritmi ricorsivi è il fattoriale.

fattoriale(n)=n*n-1*n-2*...*1

si può notare come sia semplice riscrivere iterativamente qusta funzione

//versione C++
long long int fattoriale(int n)
{
   long long int fact=1;
   for(int i=1; i<=n; ++i)
   {
      fact*=i;
   }
   return fact;
}

visto? semplice semplice, lineare, no?

Il risultato è quello, ma la formulazione matematica è diversa...

            n=0 -> 1
fattoriale(n)={
            n*fattoriale(n-1)

Entriamo ora a spiegare di cosa ha bisogno un algoritmo ricorsivo:
1)chiamata a se stesso
2)condizione di terminazione (o di arresto)

La chiamata a se stesso implica che ci sia una fine certa. La sua eventuale mancanza arriverebbe
a richiamare un numero spropositato di istanze della funzione, portando a riempire lo stack e a
bloccare l'elaboratore.

La codifica C++ dell'algoritmo del fattoriale è scrivibile così:

long long int factRic(int n)
{
   if (n==0)
   {return 1;}
   else
   {return n*factRic(n-1);}
}

Come si può vedere, il nuovo codice è molto più simile alle specifiche matematiche ed è molto più semplice.

Vediamo ora come si può creare il fattoriale in Python.

Esistono vari modi:
1) soluzione iterativa (pari pari a quella C++, non la si riscrive...)
2) soluzione funzionale (con funzione "reduce")
3) soluzione funzionale (con lambda)

Andiamo ora a spiegare gli ultimi due modi.

Soluzione "reduce"

#!/usr/bin/python
>>>n=5
>>>fattoriale=reduce(lambda x,v: x*v, range(1, n+1))
>>>fattoriale
120
>>>

Nota: questa soluzione non è il massimo da scrivere in codice reale, costringe il lettore a capire cosa fa la funzione lambda.

Spiegherò in un prossimo post cosa serve "reduce", come funziona e come si utilizza

Soluzione lambda

#!/usr/bin/python
>>>n=5
>>>fattoriale=lambda f: (not f and 1) or f*fattoriale(f-1)
>>>fattoriale(n)
120
>>>

Nota: La sintassi utilizzata fa parte di un discorso più ampio sulla programmazione funzionale, che verrà affrontato nei prossimi post, e che è possibile leggere qui
Intanto...

La funzione fattoriale valuta f. Se f è uguale a zero (qui indicato con not f, perchè in Python lo Zero è equivalente al booleano False) allora viene restituito 1, altrimenti il prodotto di f per il risultato di fattoriale con f decrementato di 1.

Posterò nel prossimo post un esempio molto più utile: la ricerca binaria.

Stay Tuned!!!