Algoritmo da ricorsivo a iterativo

[MaxDembo81]

Salve a tutti,
non ricordo/non riesco a trasformare un semplicissimo algoritmo da ricorsivo a iterativo.
L'algoritmo è il seguente

 double s(int i, int N, int A{
if (i == 0 ) return 0;
if (i == 1 ) return 1;
else return 2*N*s(i-1,N,A) + (A-N*N)*s(i-2,N,A);}

Com'era la regola generale?
E come lo si traduce questo?

Grazie e scusate la nabbanza

[clockover]

Di solito con la risorsione in coda è una stupidaggine tradurlo in iterativo! Ma per quanto riguarda il tuo algoritmo hai a che fare con due chiamate ricorsive quindi non è proprio banale la cosa!

[gugoXX]

Nel caso pero' si puo' semplificare il tutto mantenendo traccia di quanto valeva la funzione nei passi necessari precedenti.
Ovvero, durante la conta da 1 a i basta memorizzare il valore che la funzione aveva al passo precedente, e quello che aveva al passo precedente ancora.

[tuccio`]

double s(int i, int N, int A)
{

  // Il vettore S conterrà i valori del numero che vuoi calcolare
  // inizialmente S[0] = 0 e S[1] = 1.
  // Dopo di che usi gli ultimi due valori per calcolare il prossimo
  // in maniera iterativa, sovrascrivendo di volta in volta il più
  // vecchio, così da mantenere a ogni iterazione gli ultimi 2 valori
  // che ti serviranno a calcolare il prossimo numero

  double S[2] = { 0.0f, 1.0f }; // s(0, N, A) = 0, s(1, N, A) = 1

  int j; // j è il prossimo numero che devi calcolare
  for (j = 2; j <= i; j++)
  {
    // k è l'indice in cui si trova il valore s(j-2, N, A), quindi il più
    // vecchio cioè quello che sostituirai. Ovviamente l'altro valore
    // che ti serve si trova in S[1 - k]
    int k = j % 2;
    S[k] = 2*N*S[1 - k] + (A - N*N)*S[k];
  }

  // Uscito dal ciclo, il valore che cerchi è in 0 se i è pari, in 1 altrimenti
  return S[i % 2];

}

Ma perché double? non può venire un numero con la virgola :E

ps: DOVREBBE funzionare

[gugoXX]

A me la complicazione dell'array con 2 elementi soli e del riferimento se il ciclo e' pari o dispari pare un eccesso poco leggibile.

[tuccio`]

per quello c'è più commento che codice

[gugoXX]

Originariamente inviato da tuccio`

per quello c'è più commento che codice

Propongo una cosa simile
(ne' compilato ne' tantomeno testato)

double s(int i, int N, int A)
{
  if (i == 0 ) return 0;
  if (i == 1 ) return 1;
  int TM2 = 0;
  int TM1 = 1;
  int TM0;
  for (int q=2; q<=i; q++)
  {
     TM0 = 2*N*TM1 + (A - N*N)*TM2;
     TM2 = TM1;
     TM1 = TM0;
  }
  return TM0;
}

[MaxDembo81]

testiamolo

[MaxDembo81]

funzionare funziona

Mi spieghi come ci sei arrivato?

[gugoXX]

Ho scritto la logica nel primo post.

[goldorak]

Originariamente inviato da MaxDembo81

Salve a tutti,
non ricordo/non riesco a trasformare un semplicissimo algoritmo da ricorsivo a iterativo.
L'algoritmo è il seguente

 double s(int i, int N, int A{
if (i == 0 ) return 0;
if (i == 1 ) return 1;
else return 2*N*s(i-1,N,A) + (A-N*N)*s(i-2,N,A);}

Com'era la regola generale?
E come lo si traduce questo?

Grazie e scusate la nabbanza

A e N sono parametri e non cambiano nelle varie chiamate ricorsive, quindi la tua funzione s dipende solo da i.

caso base : s(0) =0, s(1)=1
caso ricorsivo : s(n) = 2Ns(i-1)+(A-N^2)s(i-2)

quindi si vede che s(n) dipende soltanto dai due valori immediatamente precedenti s(i-1) e s(i-2). Nell'algoritmo iterativo sara' sufficiente ricordarsi degli ultimi due valori calcolati per determinare il valore piu' recente.