Funzione [c]

[gliupun44]

funzione_ricorsiva(x,y){
if (y>0) {funzione_ricorsiva(x+1, y-1)}
else return x;
}

1. Dire a cosa serve la funzione_ricorsiva
2. Riscirverla in modo non ricorsivo
3. Calcolare la complessità sia di quella ricorsiva che di quella non ricorsiva.

Non so nemmeno da che parte iniziare

[apatriarca]

Per prima cosa la funzione, così com'è non compilerebbe in C. In ogni caso, direi che dovresti partire provando dei valori a caso della funzione. Per esempio, cosa succede quando y è minore o uguale a 0? Quando è maggiore? Dimmi per esempio il valore di ritorno della funzione quando vengano passati (x, -10), (x, 0) e (x, 3) per un qualche valore di \(x\).

[gliupun44]

Infatti l'avevo provata su Dev e non compila, ma l'ho trovata cosi su un testo di esame degli anni precedenti.. Beh se la y è minore/uguale di 0 la funzione ritorna x se non erro, per quanto riguarda y>0 non riesco a capire, è proprio quello il punto!

[claudio862]

Punto primo: butta via DevCpp e installa un IDE di questo decennio (Code::Blocks, Visual Studio, QtCreator, Netbeans...).
Punto secondo: per un tema d'esame forse non è necessario essere troppo formali, però mancano i tipi delle variabili e della funzione, e un'istruzione return:

int funzione_ricorsiva (int x, int y) {
    if (y > 0) {
        return funzione_ricorsiva(x+1, y-1)
    } else {
        return x;
    }
}

Se y < 0 restituisce x, quindi assumiamo che y ≥ 0.

Prova a seguirne l'esecuzione:

f(5, 9) = f(5 + 1, 9 - 1) =
  f(6, 8) = 
    f(7, 7) =
      f(8, 6) =
        f(9, 5) =
          f(10, 4) =
            f(11, 3) =
              f(12, 2) =
                f(13, 1) =
                  f(14, 0) =
                  // Ora (y > 0) è falsa, quindi non chiama
                  // più ricorsivamente f, ma restituisce x
                  = 14
                = 14
              = 14
          ... // Risale lo stack delle chiamate ricorsive
    = 14
  = 14
= 14

La funzione "sposta" passo passo 1 da y a x, finché y "contiene" almeno un 1, poi restituisce x.