#include <stdio.h>




int fib_rec( int n ) {
	
	if (n == 0)
		return 0;
	else if (n==1)
		return 1;
	else
		return fib_rec( n-1) + fib_rec(n-2);
}


int fib_dyn( int n ) {
	int A[n+1];
	A[0] = 0;
	A[1] = 1;

	int i;

	for (i=2; i <= n; i++)
		A[i] = A[i-1] + A[i-2];

	return A[n];
}

int fib_dyn2( int n ) {
	
	int n1;
	int n2;
	int nn;
	int i;

	if (n==0) return 0;
	else if (n==1) return 1;

	n2 = 0;
	n1 = 1;
	
	for (i=2; i <=n; i++) {
		nn = n2 + n1;
		n2 = n1;
		n1 = nn;	
	}

	return nn;
}

int main( void ) {
	int i;

	for (i=0; i < 30; i++) 
		printf( "%d ", fib_rec( i ) );
	printf( "\n" );
	for (i=0; i < 30; i++) 
		printf( "%d ", fib_dyn2( i ) );
	printf( "\n" );
}