// Funzioni ricursive--iterative: fattoriale, potenza, fibunacci.
#include<stdlib.h>
#include<stdio.h>
#include <time.h>

int fattoriale(int n) { if(n<=1) return 1; return n*fattoriale(n-1); }

int fattoriale_it(int n) { int res=1; while(n>1) res*=n--; return res; }

int potenza(int x, int n) { if(n==0) return 1; return x*potenza(x,n-1); }
 
int potenza_it(int x, int n) { int res=1; while(n-->0) res*=x; return res; }

int fibo(int n) { if(n<2) return 1; return fibo(n-1)+fibo(n-2); } 

int mem[50] ={0};
int fibo_mem(int n) {
  if(!mem[0]) { // init mem.
    int i; mem[0]=1; mem[1]=1; 
    for(i=2;i<50;i++) mem[i]=0; }
  if(n<2) return 1;
  if(!mem[n-1]) mem[n-1]=fibo_mem(n-1);
  return mem[n-1]+mem[n-2]; 
}

clock_t  start_ctime, finish_ctime;
p(char *s,int d) { 
  finish_ctime=clock();
  printf("%s: %d  time:%f\n",s,d,
	 ((double)(finish_ctime-start_ctime)/CLOCKS_PER_SEC)); 
  start_ctime=clock();
} 


main(int argc, char *argv[]) {
  int i,n,x;
  if(argc!=3) { printf("usage: a.out x n\n"); exit(1); }
  x=atoi(argv[1]); n=atoi(argv[2]);
  p("start...",0);
  p("fattoriale",fattoriale(n));
  p("fattoriale_it",fattoriale_it(n));
  p("potenza",potenza(x,n)); 
  p("potenza_it",potenza_it(x,n));
  p("fibo",fibo(n));
  p("fibo_mem",fibo_mem(n));
  for(i=0;i<=n;i++) printf("%d: %d\n",i,mem[i]);
}