Nota: in questo paragrafo viene trattato un argomento abbastanza avanzato e per la maggior parte delle applicazioni non sarà necessario conoscerlo. Tuttavia in alcuni casi è cosí utile da essere veramente prezioso, quindi lo presentiamo qui se vorrete approfondirlo. Basta che non vi facciate spaventare se non vi apparirà immediatamente chiaro.

Di cosa si tratta?

Malgrado quanto è stato detto in precedenza riguardo ai cicli, che rappresentano le chiavi di volta della programmazione, in effetti è possibile creare programmi senza usare un costrutto esplicito per i cicli. Alcuni linguaggi come il Lisp non dispongono di un costrutto esplicito per i cicli come FOR, WHILE, ecc. Essi usano invece una tecnica detta ricorsione. Questa tecnica risulta estremamente potente per affrontare particolari tipi di problemi, quindi la esamineremo in maggior dettaglio.

Ricorsione significa semplicemente richiamare una funzione all'interno della definizione della funzione stessa. Ad esempio la definizione dell'acronimo GNU (l'organizzazione che produce gran parte del software "libero") è ricorsiva dato che l'acronimo sta per: "GNU's Not Unix" (GNU non e' Unix, N.d.t.), ovvero GNU è una parte della definizione di GNU!

Perché la cosa possa funzionare deve esistere una condizione di terminazione tale che la funzione ad un certo punto passi ad una soluzione non ricorsiva (La definizione di GNU non risponde a questo criterio e quindi resta intrappolata in un ciclo infinito).

Vediamo un semplice esempio. La funzione fattoriale in matematica viene definita come il prodotto di tutti i numeri da 1 fino all'argomento incluso ed il fattoriale di 1 è uguale ad 1. Da un altro punto di vista si può affermare che il fattoriale di N è uguale ad N moltiplicato per il fattoriale di (N-1)

Quindi:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

Possiamo allora esprimere la stessa cosa in Python come segue:

def fattoriale(n):
    if n == 1:
        return 1
    else:
        return n * fattoriale(n-1)

In questo caso poiché N viene decrementato ogni volta ed è presente una verifica per N uguale ad uno, la funzione deve terminare.

Se volessimo scrivere la funzione fattoriale senza usare la ricorsione, dovremmo usare un po' più di codice. Occorrerebbe creare una lista di tutti i numeri da 1 ad N, e quindi fare un ciclo sulla lista che moltiplichi il totale parziale per l'elemento successivo. Provate a scrivere la funzione in questo modo per esercizio e confrontatela con quella mostrata sopra.

Ricorsione su liste

Un'altro ambito in cui la ricorsione è assai utile è nel trattamento delle liste. Ammesso che sia possibile verificare la condizione di lista vuota e generare una lista priva del primo elemento la ricorsione risulta di semplice applicazione.

Consideriamo il caso banale in cui si voglia visualizzare ciascun elemento di una lista di stringhe usando la funzione printList:

def printList(L):
    if L:
        print L[0]
        # per [1:] - vedere 'slicing' (sezioni) nel manuale di Python
        printList(L[1:])

Se L è vero - non vuoto - visualizziamo il primo elemento e quindi processiamo la parte restante della lista.

Nel caso di liste semplici è facile usare semplici cicli. Ma supponiamo che la lista sia complessa e contenga altre liste al suo interno. Se possiamo verificare la condizione che un elemento sia una lista, possiamo chiamare printList() ricorsivamente, altrimenti visualizziamo semplicemente l'elemento. Vediamolo in pratica:

def printList(L):
    # se è vuota, non fare niente
    if not L: return
    # se è una lista chiama printList sul primo elemento
    if type(L[0]) == type([]):
        printList(L[0])
    else: #non è una lista, quindi visualizzalo 
        print L[0] 
    # adesso procedi con la parte restante di L 
    printList(L[1:])

Provate adesso a fare la stessa cosa usando un costrutto di ciclo tradizionale: scoprirete che è assai difficile. L'uso della ricorsione rende relativamente semplice un compito assai complesso.

Ovviamente c'è un prezzo da pagare! La ricorsione su strutture dati di grandi dimensioni tende a consumare memoria e quindi se ne avete poca a disposizione o dovete elaborare strutture di dati molto grandi, le forme di programma più convenzionali possono essere più sicure.

Bene, adesso facciamo un passo ulteriore nell'ignoto introducendo la Programmazione ad Oggetti (Object Oriented Programming, N.d.t)

Se avete domande o suggerimenti relativi a questa pagina mandate un e-mail all'autore: alan.gauld@yahoo.co.uk o al traduttore italiano: lfini@arcetri.astro.it