#include <stdio.h>
#include <string.h>

#define CACHE_SIZE 1000			// size of cache table for enhanced fibonacci recursion algorithm
#define FIB_CLASS 4				// size of temporary shift allocation table. also defines fibonacci number class


double c_table[CACHE_SIZE];		// cache table for enhanced fibonacci recursion algorithm


// initialize any given table => fills all elements with 0's
void init_table (double array[], int len) {
	int i;
	for (i=0; i < len ; i++ ) array[i]=0;
}

// shifts given table, last element is replaced with 0
void shift_table (double array[], int len) {
	int i;
	for (i=0; i < len-1 ; i++ ) array[i]=array[i+1];
	array[len-1]=0;
}

// returns sum of given table
double sum_table (double array[], int len) {
	int i; double result=0;

	for (i=0; i < len ; i++ ) result+=array[i];
	return(result);
}


// fibonacci numbers, recursion algorithm
double fib_rek (int n) {
	int i;
	double result;

	if (n < FIB_CLASS-1) return(0);
	else if (n == FIB_CLASS-1) return(1);
	else {
		for (i=1; i <= FIB_CLASS ; i++) result+=fib_rek(n-i);
		return(result);
	}
}

// fibonacci numbers, enhanced recursion algorithm
double fib_rek_e(int n) {
	int i;

	if (n < FIB_CLASS-1) return(0);
	else if (n == FIB_CLASS-1) return(1);
	else {
		if (!c_table[n]){
			for (i=1; i <= FIB_CLASS ; i++ ) c_table[n]+=fib_rek_e(n-i);
		}else{
			return(c_table[n]);
		}
	}
}

// fibonacci numbers, iterative algorithm
double fib_it (int n) {
	int i;
	double it_table[FIB_CLASS];	// cache table for 4 previous results
	double x;						// temporary result

	if (n < FIB_CLASS-1) return(0);
	else if (n == FIB_CLASS-1) return(1);
	else {
		init_table(it_table,FIB_CLASS);
		it_table[FIB_CLASS-1]=1;

		for (i=FIB_CLASS+1; i <= n ; i++ ){
			x=sum_table(it_table,FIB_CLASS);
			shift_table(it_table,FIB_CLASS);
			it_table[FIB_CLASS-1]=x;
		}

		return(sum_table(it_table,FIB_CLASS));
	}
}

void help (void) {
	fprintf(stderr,"Usage: rek-iter {algorithm} {size}\n");
	fprintf(stderr,"\t1 - recursive algorithm\n");
	fprintf(stderr,"\t2 - enhanced recursive algorithm\n");
	fprintf(stderr,"\t3 - iterative algorithm\n");
	fprintf(stderr,"\t4 - iterative algorithm with stack\n");
}

int main (int argc, char *argv[]) {
	int i,choice,x;
	
	if (argc < 3){
		help();
		return 1;
	}

	choice=atoi(argv[1]);
	x=atoi(argv[2]);


	// what to do?
	switch (choice){
	case 1:
		printf("Value of %d-th Fibonacci number (class %d) is: %0.lf\n",x,FIB_CLASS,fib_rek(x));
		break;
	case 2:
		// init cache table
		if (x > CACHE_SIZE){
			fprintf(stderr,"Values over %d are not supported.\n",CACHE_SIZE);
			return 1;
		}
		init_table(c_table,CACHE_SIZE);
		printf("Value of %d-th Fibonacci number (class %d) is: %0.lf\n",x,FIB_CLASS,fib_rek_e(x));
		break;
	case 3:
		printf("Value of %d-th Fibonacci number (class %d) is: %0.lf\n",x,FIB_CLASS,fib_it(x));
		break;
	case 4:
		printf("Value of %d-th Fibonacci number (class %d) is: %0.lf\n",x,FIB_CLASS,fib_rek_e(x));
		break;
	default:
		fprintf(stderr,"Unknown algorithm.\n");
		break;
	}
	return 0;
}