#include <stdio.h>

#define N 50

/**
 * Renvoie le couple (F_k, F_k+1)
 */
void fiboRec(int aa[N], int k){
	if(k<=1)aa[k] = 1;
	else aa[k] = aa[k-2]+aa[k-1];
	if(k+1<N)fiboRec(aa, k+1);
}

/**
 * Est-ce ce qui a été demandé ? Si oui, c'est très long.
 */
int fiboRecMoche(int k){
	if(k<=1) return 1;
	return (fiboRecMoche(k-1) + fiboRecMoche(k-2));
}

void fiboPlain(int aa[N]){
	aa[0] = aa[1] = 1;
	for(int k=2;k<N;k++)
		aa[k] = aa[k-2] + aa[k-1];
}

int main() {
	
	int fiboArr[N];
	int fiboArrRec[N];
	
	fiboRec(fiboArrRec,0);
	fiboPlain(fiboArr);
	
	printf("Fibo récursif : %d\n", fiboArrRec[N-1]);
	printf("Fibo non récursif : %d\n", fiboArr[N-1]);
	
	// Avec cette ligne ça met trop de temps. Complexité exponentielle, miam miam. 
	printf("Fibo très moche : %d\n", fiboRecMoche(N-1));
	
	return 0;
}