#include <stdio.h>

#define N 100 // Largest Fibonacci number that can be computed

int Fib_loop();
int Fib_rec();
int Fib_rec_imp();

int main(int argc, char *argv[])
{
	int n;
	int method; // represents the method of computation

	if (argc != 3) {
		printf("ERROR: Usage is Fib <number> <method>\n");
		return 0;
	}

	sscanf(argv[1], "%d", &n);
	sscanf(argv[2], "%d", &method);

	printf("Fibonacci number #%d = ", n);

	if (method == 1)
		printf("%d\n", Fib_loop(n));
	else if (method == 2)
		printf("%d\n", Fib_rec(n));
	else 
		printf("%d\n", Fib_rec_imp(n));
}


/* Computes nth Fibonacci number using a loop */
int Fib_loop(int n)
{
	int F[N];

	F[0] = 1; // Set the first two numbers
	F[1] = 1;

	for (int m = 2; m <= n; m++)
		F[m] = F[m-1] + F[m-2];

	return F[n];
}


/* Computes nth Fibonacci number using recursion */
int Fib_rec(int n)
{
	if ((n == 0) || (n == 1)) // first two numbers
		return 1;

	return Fib_rec(n-1) + Fib_rec(n-2);
}
	

int F[N]; // Stores Fibonacci sequence
int m = 1; // First m Fibonacci numbers have been computeD

int Fib_rec_imp(int n)
{
	if ((n == 0) || (n == 1)) {
		F[n] = 1;
		return F[n];
	}

	if (n > m) { // F[n] not computed yet
		F[n] = Fib_rec_imp(n-1) + Fib_rec_imp(n-2);
		m = n;
	}

	return F[n];
}