#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int Lucas ( unsigned int n , int a , int b )
{
   if (n == 0) return 0;
   if (n == 1) return 1;
   return a * Lucas(n-1,a,b) - b * Lucas(n-2,a,b);
}

int LucasIterative ( unsigned int n , int a , int b )
{
   int i, U_1, U_2, U;

   if (n == 0) return 0;
   if (n == 1) return 1;
   U_2 = 0; U_1 = 1;
   for (i = 2; i <= n; ++i) {
      U = a * U_1 - b * U_2;
      U_2 = U_1;
      U_1 = U;
   }
   return U;
}

int main ()
{
   int a, b, U;
   unsigned int n;
   time_t t1, t2;

   printf("a = "); scanf("%d", &a);
   printf("b = "); scanf("%d", &b);
   printf("n = "); scanf("%u", &n);

   printf("\nRecursive function: "); fflush(stdout);
   t1 = clock(); U = Lucas(n,a,b); t2 = clock();
   printf("U(%u) = %d\n", n, U);
   printf("Time taken = %lf sec\n", (double)(t2 - t1) / (double)CLOCKS_PER_SEC);

   printf("\nIterative function: "); fflush(stdout);
   t1 = clock(); U = LucasIterative(n,a,b); t2 = clock();
   printf("U(%u) = %d\n", n, U);
   printf("Time taken = %lf sec\n", (double)(t2 - t1) / (double)CLOCKS_PER_SEC);

   exit(0);
}