Implementazione dinamica di una funzione definita ricorsivamente (Appello Aprile 2010)

Sia data la funzione F così definita :

Si richiede di implementare in linguaggio C:

• Una funzione Fr che calcoli F (n, k);
• Una funzione Frd che calcoli F (n, k) in O(n2 );

Implementazione ricorsiva

int F(int n, int k)
{
    if(n*k==0)return n+k;
    return F(n,k-1)+ F(n-1,k)+ F(n-1,k-1);
}

La fuzione viene implementata applicando semplicemente la formula di ricorsione

Implementazione iterativa

int Fi(int n, int k)
{
    int **v=malloc(sizeof(int)*(n+1)*(k+1));
    int x=Fi_implementation(n,k,n+1,k+1,v);
    free(v);
    return x;
}

int Fi_implementation(int n, int k, int a, int b,int v[a][b])
{
    int r,c,x;

    for(r=0; r<=n; r++)
    {
        for(c=0; c<=k; c++)
        {
            if(r*c==0)v[r]1=r+c;
            else
                v[r]1=v[r][c-1]+v[r-1]1+v[r-1][c-1];
        }
    }
    x=v[n][k];
    return v[n][k];
}

Il calcolo di ogni elemento n,k richiede il calcolo di tutti gli elementi y<n , n<k e questi elementi vengono usati più di una da tutti gli elementi superiori e a destra, salvandoli in una matrice è possibile ridurre la complessità a O(n*k) occupando O(n*k) memoria.
per facilitare la leggibilità del codice si usa una funzione di appoggio che permette di definire il vettore con le sue dimensioni, altrimenti passando semplicemente un puntatore doppio si dovrebbero calcolare gli indirizzamenti esplicitamente.