Archive

Posts Tagged ‘ricorsione’

Tail Recursion vs. Direct Recursion provare per credere

September 3, 2009 Leave a comment

Se avete seguito qualche corso di programmazione o avete letto qualche guida a riguardo, vi sarà sicuramente capitato di sentire parlare di “ricorsività”.

Il concetto di ricorvisità è molto semplice: il problema da risolvere viene suddiviso in sottoproblemi piu semplici le cui soluzioni, elaborate tra loro, permettono di arrivare alla soluzione del problema principale.

Ricordo che durante il mio primo anno di università il docente ci introdusse la ricorsività tramite l’esempio della funzione fattoriale.

Secondo Wikipedia “In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi.

In pratica il fattoriale di un numero (rigorosamente intero e positivo) è il prodotto tra tale numero e il risultato dell’operazione di fattoriale eseguita sul numero ad esso precedente (per definizione il fattoriale di 0 è 1).

Esempio pratico!

3! = 3 * 2! = 3 * (2 * 1!) = 3 * (2 * (1 * 0!)) = 3 * (2 * (1 * 1))
3! = 6

Vediamo ora quale potrebbe essere una possibile implementazione in erlang:

-module(fattoriale).
-export([calcola/1]).

calcola(0) ->
    1;
calcola(Numero) when Numero > 0 ->
    Numero * calcola(Numero -1).

Analizziamo la parte di tale modulo inerente alla funzione calcola. La prima cosa che forse non sapete di erlang, e’ che quando invocate una funzione in un modulo, erlang cerca di “far combaciare” la vostra chiamata con tutte le funzioni con lo stesso nome che esistono in tale modulo….cerco di spiegarmi meglio con un esempio pratico:

L’utente (cioe’ io :) ) chiama dalla riga di comando la funzione fattoriale:calcola(3)

A questo punto la erlang virtual machine cerca nel module fattoriale tutte le funzioni che si chiamano calcola….nel modulo sono presenti due dichiarazioni per la funzione calcola: la prima viene scartata in quanto la nostra chiamata non ha come parametro 0, mentre la seconda e’ utilizzata, in quanto il valore passato rispetta la proprieta’ di essere un valore maggiore di zero. Se avessimo chiamato la funzione con un valore negativo, la shell ci avrebbe dato come output un errore, in quanto non esisteva una funzione che soddisfasse tale chiamata.

La cosa veramente simpatica dell’erlang e’ che se passavate come parametro un atom, ad esempio ‘a’ la vostra chiamata alla funzione sarebbe stata valida in quanto in erlang si possono comparare con > e < diversi tipi di variabili…detto cio’ avreste comunque ottenuto un errore perche’ l’operazione di moltiplicazione non e’ consentita con gli atoms! (comparate gli errori!)

Questo per la parte riguardante la ricorsione diretta…non so se vi siete accorti di una cosa…utilizzando questo tipo di ricorsione dobbiamo arrivare al risultato per il problema minore e poi ripercorrere la funzione al contrario…cio’ introduce una certa difficolta’ computazionale che gli sviluppatori del linguaggio erlang hanno cercato di risolvere con la tail recursion.

Ecco un simpatico esempio in erlang di funzione fattoriale risolta con tail recursive functions:

-module(fattoriale).
-export([calcola/1]).

calcola(0) -> 1;
calcola(Numero) when Numero > 0 ->
    calcola(Numero, 1).

calcola(1, Totale) ->
    Totale;
calcola(Numero, Parziale) ->
    calcola(Numero -1, Parziale * Numero).

Esattamente come prima all utente viene garantita una sola funzione (calcola con un argomento di ingresso). Come prima se il valore in ingresso e’ zero diamo come output 1, ma se la il valore di ingresso e’ un valore maggiore di 0, invochiamo la funzione calcola a due argomenti, ponendo il secondo argomento a 1.

Tale funzione e’ interna (non disponibile a chiamate esterne al modulo stesso) e ha un match (combacia) solo con la funzione calcola(Numero, Parziale). Alla prima esecuzione di tale funzione il valore della variabile Numero e’ il numero da elaborare, mentre il valore della variabile Totale e’ uno.  Tale funzione non fa altro che richiamare se stessa passando come parametri il Numero stesso diminuito di un elemento e il valore di Parziale moltiplicato per Numero. Quando arriviamo ad avere una chiamata a calcola con Numero uguale a 1, la funzione calcola(1, Totale) verra’ eseguita (essendo la funzione che combacia) e il valore di Totale verra’ riportato in uscita.

Nel gergo di erlang la variabile Parziale viene detta accumulatore, in quanto in tale variabile viene immagazinato il risultato parziale; con tale approccio al problema non si ha il bisogno di compiere due cicli (uno in avanti e uno indietro) in quanto arrivati all’ultima chiamata, il valore che vogliamo ottenere e’ gia presente nell’accumulatore!

Uno dei miti di erlang (http://erlang.org/doc/efficiency_guide/myths.html) consiste nell’asserire che le funzioni tail recursive sono molto piu veloci delle funzioni full recursive….ora questo forse era vero in passato…ma al momento a mio avviso tale affermazione e’ superata e la scelta tra le due dovrebbe essere fatta per altri motivi…vedi stilistica del codice o tipo di problema. Personalmente preferisco le tail recursive…ma questa e’ solo l’idea di un niubbo….

Un’interessante cosa da provare e’ eseguire un semplice bechmarking sulle due precedenti implementazioni del modulo fattoriale…cercando di capire quale delle due e’ piu’ veloce.

Possiamo effettuare tale benchmarking tramite la funzione tc/3 messa a disposizione dal modulo timer.

Tale funzione prende come ingresso tre parametri: il modulo, la funzione e l’argomento. Output di tale funzione e’ una tupla contenente il tempo impiegato per eseguire tale funzione (in microsecondi) ed il risultato ottenuto.

Cerchiamo di calcolare il fattoriale di 1000 e vediamo quale e’ la differenza tra le due tempistiche. (I numeri sono abbastanza grandi quindi riporto in una tupla commentata sotto ogni esecuzione il risultato che ho ottenuto )

1> l(fattoriale).
2> l(fattoriale2). %% cambiato nome modulo per tail recursion in fattoriale2
3> {Time1, Value1} = timer:tc(fattoriale, calcola, [1000]).
%%{Time1, Value1} = {16859000, numero astronomico}

4>{Time2, Value12 = timer:tc(fattoriale2, calcola, [1000]).
%%{Time2, Value2} = {13485000, numero astronomico}.

Come avrete capito l’implementazione direct recursive ha impiegato circa 17 secondi mentre la tail recursive ha impiegato un po piu di 13 secondi….tutto cio’ mi porta a dire che in questo caso il cane nella foto sottostante ha effettivamente ragione nel preferire la tail recursion!

Anche questo cane ama la ricorsività

Anche questo cane ama la tail recursion

Categories: Erlang Tags: ,
Follow

Get every new post delivered to your Inbox.

Join 25 other followers