#include <stdio.h>

/* Déclaration de la fonction fibonacci() :
Fonction récursive qui calcule et renvoie le nombre de rang n de la suite de Fibonacci
- paramètre n : rang du nombre
- valeur de retour : le nombre de rang n de la suite de Fibonacci*/
int fibonacci(int n);


/* Déclaration de la fonction fibonacci_bis() :
Fonction non récursive qui calcule et renvoie le nombre de rang n de la suite de Fibonacci
- paramètre n : rang du nombre
- valeur de retour : le nombre de rang n de la suite de Fibonacci*/
int fibonacci_bis(int n);


int main()
{
    int n;
	printf("--> saisir le rang n : ");
	scanf("%d", &n);

    printf("Version recursive :\n");
    for (int i = 0; i <= n; ++i)
    {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    printf("\nVersion non recursive :\n");
    for (int i = 0; i <= n; ++i)
    {
        printf("%d ", fibonacci_bis(i));
    }
    printf("\n");
    return 0;
}

// Définition de la fonction fibonacci() 
int fibonacci(int n)
{
    int res;
    if (n == 0) // condition initiale
    {
        res = 0;
    }
    else if (n == 1) // condition initiale
    {
        res = 1;
    }
    else
    {
        res = fibonacci(n-1) + fibonacci(n-2);
    }
    return res;
}

// Définition de la fonction fibonacci_bis()
int fibonacci_bis(int n)
{
    int fi;
    if (n == 0)
    {
        fi = 0;
    }
    else if (n == 1)
    {
        fi = 1;
    }
    else
    {
        int fi_1 = 1, fi_2 = 0; 
		// fi_1 sert à mémoriser la valeur de F au rang i-1
		// fi_2 sert à mémoriser la valeur de F au rang i-2
		// fi représente la valeur de F au rang i
		
		// lors du premier tour de boucle (i = 2), on veut calculer fi = F2
		// donc il faut initialiser fi_1 à F1 = 1 et fi_2 à F0 = 0
        for (int i = 2; i <= n; ++i)
        {
            fi = fi_1 + fi_2;
			// mise à jour de fi_2 et fi_1 pour le prochain tour de boucle
            fi_2 = fi_1;
            fi_1 = fi;
        }
    }
    return fi;
}