/*
	 HomeWork5: funzioni ricorsive
*/
#include <stdio.h>

/* struct usata da fibonacci_efficiente (versione che torna una coppia) */
typedef struct {
		int last;
		int prev;
} coppia;

/* array che 'ricorda' i valori calcolati (solo fino a 50) */
int memo[50] = { 0 };
int memo1[50] = { 0 };

/* prototipi delle funzioni usate */
void traccia(int x, int p);
void traccia2(int x, int y, int p);
int fattoriale(int x,int p);
int fibonacci(int x, int p);
coppia fibonacci_efficiente(int x, int p);
int fibonacci_memo(int x, int p);
int quarantadue(int x, int p);
int emme(int x, int p);		
int emme_memo(int x, int p);		/* ricorda la sola m 		*/
int emme_memo_memo(int x, int p);	/* ricorda sia m che g 		*/
int GCD(int x, int y, int p);

/************************************************************************/
int main(int argc, char * argv[]) {
	/* dichiarazioni */
	int x = 0,
		 y = 0;
	int prof = 1;	/* profondita` */
	 
	/* controllo l'input */
	if (argc>4 || argc<2) 
		 return 1;
	if (argv[1][0] != '-') 
		 return 1;
	
	/* leggo 2' (e 3') argomento */
	if (argc>2)
		 x = atoi(argv[2]);
	if (argc>3)
		 y = atoi(argv[3]);
	
	/* seleziono la funzione a seconda del secondo carattere dell'opzione */
	switch (argv[1][1]) {
	case 'f':
		 y = fattoriale(x,prof);
		 printf("%d\n",y);
		 break;
	case 'F':
		 y = fibonacci(x,prof);
		 printf("%d\n",y);
		 break;
	case 'E':
		 y = fibonacci_efficiente(x,prof).last;
		 printf("%d\n",y);
		 break;
	case 'A':
		 y = fibonacci_memo(x,prof);
		 printf("%d\n",y);
		 break;
	case 'G':
		 if (x>y)
		y = GCD(y,x,prof);
		 else
		y = GCD(x,y,prof);
		 printf("%d\n",y);
		 break;		 
	case 'h':
		 y = quarantadue(x,prof);
		 printf("%d\n",y);
		 break;
	case 'v':
		 /* dati personali */
		 printf("Andrea\nSterbini\n02\n02\n1961\nsterbini@dsi.uniroma1.it\n");
		 break;
	case 'm':
		 y = emme(x,prof);
		 printf("%d\n",y);
		 break;
	case 'M':
		 y = emme_memo(x,prof);
		 printf("%d\n",y);
		 break;
	case 'D':
		 y = emme_memo_memo(x,prof);
		 printf("%d\n",y);
		 break;
	default:
		 return 1;
	}
	return 0;
}

/*************************************************************************/
void traccia(int x, int p)
{
	 int i;
	 for (i=0;i<p;i++)
	printf("*");
	 printf(" %d\n",x);
}

void traccia2(int x, int y, int p)
{
	 int i;
	 for (i=0;i<p;i++)
	printf("*");
	 printf(" %d %d\n",x,y);
}

/*************************************************************************/
int fattoriale(int x,int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return x * fattoriale(x-1,p+1);
}

/*************************************************************************/
/*
 * fibonacci-ricorsiva-di-Sterbini-che-non-si-ricorda-il-caso-base
 */
int fibonacci(int x, int p)
{
	 traccia(x,p);
	 if (0==x || 1==x)
	return 1; 
	 else
	return fibonacci(x-1,p+1) + fibonacci(x-2,p+1);
}

/* questa implementazione torna i due valori F(n) e F(n-1) da cui calcola
 * F(n+1) e F(n)
 * usiamo una struct 'coppia' per tornare i due valori
 */
coppia fibonacci_efficiente(int x, int p)
{
	 int y;
	 coppia c={1,1};
	 traccia(x,p);
	 if (x>1) {
	c = fibonacci_efficiente(x-1,p+1);
	y = c.prev + c.last;
	c.prev = c.last;
	c.last = y;
	 };	
	 return c;
}

/* questa funzione 'ricorda' i valori calcolati in modo da non doverli
 * ricalcolare
 */
int fibonacci_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);
	 
	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 /* altrimenti lo calcolo nel modo standard */
	 if (x == 0 || x == 1) 
	result = 1;
	 else
	result = fibonacci_memo(x-1, p+1) + fibonacci_memo(x-2, p+1);

	 /* e mi ricordo il risultato */
	 memo[x] = result;
	 return result;
}

/*************************************************************************/
int quarantadue(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 42;
	 else
	return 2*x + quarantadue(x-1,p+1);
}

/*************************************************************************/
/*
#  m(0) = 0
# m(x) = m(x-1) + 2*g(x)
# g(0) = 1
# g(x) = g(x-1) - 2*m(x-1) 
*/

int gi(int x, int p); /* prototipo necessario per la chiamata doppiamente ricorsiva*/
int emme(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 0;
	 else
	return emme(x-1,p+1) + 2 * gi(x,p+1);
}

int gi(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return gi(x-1,p+1) - 2 * emme(x-1,p+1);
}


/* versione che memorizza i risultati della sola 'm' */
int gi_memo(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return gi_memo(x-1,p+1) - 2 * emme_memo(x-1,p+1);
}

int emme_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 if (0==x)
	result = 0;
	 else
	result = emme_memo(x-1,p+1) + 2 * gi_memo(x,p+1);
	
	 memo[x] = result;
	 return result;
}

/* versione che memorizza i risultati sia di 'm' che di 'g' */
int gi_memo_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo1[x] != 0)
	return memo1[x];

	 if (0==x)
	result = 1;
	 else
	result = gi_memo_memo(x-1,p+1) - 2 * emme_memo_memo(x-1,p+1);

	 memo1[x] = result;
	 return result;
}

int emme_memo_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 if (0==x)
	result = 0;
	 else
	result = emme_memo_memo(x-1,p+1) + 2 * gi_memo_memo(x,p+1);
	
	 memo[x] = result;
	 return result;
}

/*************************************************************************/
/*
 * Minimo Comune Multiplo calcolato ricorsivamente 
 * usando l'algoritmo di Eulero
 */
int GCD(int x, int y, int p) {
	 traccia2(x, y, p);
	 
	 if (x == 0)
	return y;
	 else
	return GCD(y%x,x,p+1);
}