PROCEDURE E FUNZIONI RICORSIVE

Ogni linguaggio di programmazione permette di definire funzioni e procedure ricorsive, cioè che richiamano se stesse.
Notare che il termine ricorsivo potrebbe essere sviante, è meglio considerarle definite per induzione.

Una funzione F con un parametro che varia nell'insieme INP è definita per induzione se

esiste un ordine > totale ben fondato su INP, cioè esiste un elemento minimo BASE e per ogni i appartenente a INP, l'insieme dei j appartenenti a INP minori di i è finito
F(BASE) = EXP, dove F non appare in EXP
per i > BASE, F(i) = EXP', dove F può apparire in EXP' ma con parametri attuali j tali che i > j.

Ogni funzione definita per induzione come sopra può essere realizzata come una funzione/procedura ricorsiva in un linguaggio di programmazione.

Vediamo alcuni esempi

FATT(n) = 1 se N <= 0
FATT(n) = n * FATT(n-1) altrimenti
OR(n) = 2 * OR(n-1) + OR(n-1)
O1(n) = 7 se n <= 7
O1(n) = 7 * O1(n-7) altrimenti
O2(0) = 0
O2(n) = O2(n+1) * O2(n) se n > 0

1 e 3 sono definizioni induttive, mentre 2 e 4 non vanno bene (nel primo caso manca la base e nell'altro a destra troviamo delle chiamate su elementi maggiori del parametro).

IN C è molto semplice realizzare funzioni ricorsive, basta richiamarle all'interno del loro body.

ESEMPI

Fattoriale

int Fatt(int n)
 {    
    if(n <= 0) 
        return 1;
    else 
        return n * Fatt(n-1);
}

Torri di Hanoi

Le torri di Hanoi sono un antico rompicapo indiano, se volete provare a giocare premere qui.

Consideriamo il problema Hanoy(N) che consiste nel trovare le istruzioni per muovere n dischi da un piolo, sia A, ad un'altro, sia B, e poi cerchiamo di darne una soluzione per mezzo di una funzione definita per induzione su N.

BASE: N = 1. In questo caso basta spostare l'unico disco dal piolo A al piolo B.
PASSO INDUTTIVO: Spostiamo N-1 dischi sul terzo piolo (diverso da quello di partenza e da quello di arrivo), sia C, sappiamo farlo per l'ipotesi induttiva; spostiamo l'ultimo disco su B, e poi spostiamo gli N-1 dischi da C a B, sappiamo farlo per l'ipotesi induttiva.

Vediamo ora la procedura C che stampa le istruzioni per risolvere il rompicapo con N dischi

 void Hanoy(int n_dischi, int partenza, int arrivo)
 {    
    if(n_dischi < 1 || partenza == arrivo) 
        printf("ERRORE\n");
    else 
        if(n_dischi == 1) printf("Muovi disco da %d a %d\n",partenza, arrivo);
        else {   int altro_piolo = 6 - partenza - arrivo;
                 Hanoy(n_dischi -1, partenza, altro_piolo);
                 printf("Muovi disco da %d a %d\n",partenza, arrivo);
                 Hanoy(n_dischi -1, altro_piolo, arrivo);
              }
 }

ESERCIZI

Scrivere una funzione C per stampare una mossa e utilizzarla per dare una nuova versione della funzione Hanoy.
Dare una funzione ricorsiva per stampare i numeri di Fibonacci; confrontare poi questa soluzione con quella iterativa data precedentemente discutendo i relativi meriti e demeriti.
Dare una procedura C per la funzione induttiva n.3 definita precedentemente.