Controllo

Controllo

Ricorsione

Metodo alternativo all'iterazione. Una funz (procedura) e' ricorsiva se e'definita in termini di se stessa.

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

la definizione di una funzione ricorsiva e' analoga alla definizione induttiva di una funzione:

• il valore F su un argomento e'definito in termini dei valori di F su argomenti piccoli.

Nei programmi sono possibili definizioni non "corrette":

int fie1(int n){
    if (n==1) return fie1(1);
}

ovvero fie(1) = fie(1)

Nota: la ric e' possibile in qualisiasi ling che permetta:

• funz (o procedure) che possono chiamare se stesse
• gestione dinamica della mem (pila)

Ricorsione in coda

Una chiamata di g in f si dice chiamata in coda (o tail call) se f restituisce il val restituito da g senza ulteriore computazione. Quindi f e'tail recursive se contiene solo chiamate in coda:

function tail_rec (n: integer): integer
begin … ; x:= tail_rec(n-1) end

Non ric in coda:

function non_tail_rec (n: integer): integer
begin … ; x:= non_tail_rec(n-1); y:= g(x) end

Nota:

1. non server allocazione dinamica della mem con pila: basta un unico RdA
2. Piu' efficiente
3. Possibile la generazione di codice tail-recursive usando continuation passing style

Es. Caso del fattoriale

Converto la seguente funz ric in funz ric in coda:

int fatt(int n){
    if (n<=1) return 1;
    else return n* fattrc(n-1,n*res);
}

Sol:

int fattrc(int n, int res){
    if (n<=1) return res;
    else return fattrc(n-1,n*res);
}

Altro es:

Numeri di fibonacci Definzione induttiva:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2)

Versione con ric non in coda

int fib(int n){
    if (n==0)
        return 1;
    else
        if(n==1)
            return 1;
        else
            return fib(n-1) + fib(n-2);
}

Complessita' lineare in tempo e spazio (O(n))

Versione ric in coda:

int fibrc(int n, int res1, int res2){
    if (n==0)
        return res2;
    else
        if(n==1)
            return res2;
        else
            return fibrc(n-1,res2,res1+res2);
}

Complessita':

• in tempo lineare in n
• in spazio costante (un solo RdA)