Lezione 3: ricorsione

Inserito da D4rKr0W il Lun, 07/21/2008 - 03:10

La ricorsione è un modo classico di affrontare un problema riducendolo a un insieme di sottoproblemi dello stesso tipo, ma più semplici da risolvere.

In generale una procedura ricorsiva ha la forma:

        void foo (tipoParametro p) {
          if (p == casoBase1) 
               comandoBase1
          else 
               …… 
          foo(p’) /* p’ è un’espressione di tipo tipoParametro tale che p’ < p */
          …… 
     }

Una procedura ricorsiva:

Chiama se stessa ricorsivamente.
Ha una o più condizioni di terminazione.
Ad ogni chiamata ci si avvicina alla condizione di terminazione.

Esempi di funzioni ricorsive

Uso di funzioni ricorsive per implementare funzioni matematiche che ammettono una definizione induttiva.

sum(n, m) =

n
- se m = 0
sum(n, m -1) + 1
- se m > 0

int sum (int add1, int add2) {
 
     int somma;
     if (add2 == 0)
          somma = add1;
     else
          somma = sum(add1, add2 -1) + 1;
     return somma;
}

Somma con n e m interi.

sum(n, m) =

n
- se m = 0
sum(n, m -1) + 1
- se m > 0
sum(n, m + 1) -1
- se m < 0

n è dispari ?

dispari(n) =

1
- se n = 1
0
- se n = 0
dispari(n -2)
- se n > 1

Definizione di una funzione ricorsiva

Formalmente una funzione ricorsiva deve essere definita nel dominio induttivamente. Se si utilizza l’induzione naturale
- Definire la funzione su 0.
- Supponendo la funzione definita su n si definisce su n+1.
Per definire funzioni ricorsive su domini diversi dai naturali si usa il principio di induzione ben fondata.
Un insieme S è ben fondato rispetto ad una relazione di precedenza < se in (S, <) non esistono catene infinite decrescenti.
- Si definisce la funzione sui casi minimali.
- Supponendo definita la funzione per tutti gli n < m si definisce anche su m, per qualsiasi m elemento del dominio.

Esercizi

Dare una definizione induttiva delle seguenti funzioni e scrivere la corrispondente funzione ricorsiva in C.

Siano b ed e interi non negativi. Definire la potenza: pot(b, e).
Siano n e m due interi non negativi. Definire il prodotto: prod(n, m).
Sia n un intero non negativo e k un intero positivo. Definire il resto della divisione di n per k: resto(n, k).

darkrow.net