[C] Esercizio con ricorsione ed iterazione

[raissa95]

Ragazzi mi date una mano? Devo scrivere questo programma sia con la ricorsione e sia con l'iterazione.
Scrivere un programma C che consenta di calcolare l’elemento i-esimo della sequenza caratterizzata dalla
definizione ricorsiva:

s(0) = 0

se n è dispari:
s(n)= 1 + sommatoria di tutti gli s(i) per i da zero ad (n-1)

se n è pari:
s(n)= sommatoria di tutti gli s(i) per i da zero ad (n-1)

Implementare sia la soluzione ricorsiva sia quella iterativa e discutere sull’efficienza di entrambi gli
approcci.
Grazie in anticipo

[apatriarca]

Nessuna idea? Devi implementare esattamente quelle ricorsioni o puoi osservare che
\[ s(2\,n) = \sum_{i=0}^{2\,n-1} s(i) \text{ e } s(2\,n-1) = 1 + \sum_{i=0}^{2\,n-2} s(i) \]
da cui
\[ s(2\,n) - s(2\,n-1) = s(2\,n-1) - 1 \implies S(2\,n) = 2\,s(2\,n-1) - 1. \]
Prendendo invece \(s(2\,n+1) = 1 + \sum_{i=0}^{2\,n} s(i)\) otteniamo
\[ s(2\,n+1) - s(2\,n) = 1 + s(2\,n) \implies s(2\,n+1) = 1 + 2\,s(2\,n). \]