/* Code to demonstrate procedure calls */
#include <stdio.h>
#include <stdlib.h>

/* Pure leaf procedure */
long prod(long x, long y)
{
    return x*y;
}

/* Nonleaf with no local storage */
long mul_2p1(long x, long y)
{
    long u = prod(y, x);
    return u + 1;
}

/* Leaf with local storage */
long val_loc(long x, long y, int i)
{
    long vals[2] = { x*y, x+y };
    i &= 0x1;
    return vals[i];
}

/* Nonleaf with local storage for intermediate results */
long mul_3(long x, long y, long z)
{
    long u = prod(x, y);
    long v = prod(u, z);
    return v;
}

/* Nonleaf with local storage for intermediate results */
long mul_3p1(long x, long y, long z)
{
    long u = prod(x, y);
    long v = prod(u, z);
    return v + 1;
}

/* Leaf with pointer argument */
void store_prod(long x, long y, long *dst)
{
    long u = x * y;
    *dst = u;
}

/* Nonleaf with local storage for address generation */
long mul_2s(long x, long y)
{
    long u;
    store_prod(x, y, &u);
    return u;
}

/* Local storage for intermediates & address generation */
long mul_3s(long x, long y, long z)
{
    long u;
    store_prod(x, y, &u);
    store_prod(u, z, &u);
    return u;
}

long mul_list(long a[], int cnt)
{
    long result = 1L;
    int i;
    for (i = 0; i < cnt; i++)
	result = prod(result, a[i]);
    return result;
}

/* Recursion */
long mul_list_r0(long a[], int cnt)
{
    if (cnt <= 0)
	return 1L;
    else {
	long last = a[cnt-1];
	long p1 = mul_list_r0(a, cnt-1);
	return p1*last;
    }
}

/* Recursion */
long mul_list_r1(long a[], int cnt)
{
    if (cnt <= 0)
	return 1L;
    else if (cnt == 1)
	return a[0];
    else {
	long last = a[cnt-1];
	long p1 = mul_list_r1(a, cnt-1);
	return p1*last;
    }
}

/* Tail Recursion (destructive) */
long mul_list_r2(long a[], int cnt)
{
    if (cnt <= 0)
	return 1L;

    else if (cnt == 1)
	return a[0];
    else {
	a[cnt-2] *= a[cnt-1];
	return mul_list_r2(a, cnt-1);
    }
}

/* Divide & conquer recursion */
long mul_list_r3(long a[], int cnt)
{

    if (cnt <= 0)
	return 1L;
    else if (cnt == 1)
	return a[0];
    else {
	int cd2 = cnt >> 1;
	long p1 = mul_list_r3(a, cd2);
	long p2 = mul_list_r3(a+cd2, cnt-cd2);
	return p1*p2;
    }
}

int cnt_even(unsigned bits);
int cnt_odd(unsigned bits);

int cnt_even(unsigned bits)
{
    unsigned nbits = bits >> 1;
    int nval;
    if (bits == 0)
	return 0;
    if (bits & 0x1)
	nval = cnt_even(nbits);
    else
	nval =  cnt_odd(nbits);
    return nval;
}

int cnt_odd(unsigned bits)
{
    unsigned nbits = bits >> 1;
    int nval;
    if (bits == 0)
	return 0;
    if (bits & 0x1)
	nval = cnt_even(nbits);
    else
	nval = cnt_odd(nbits);
    return nval+1;
}

int cnt_bits(unsigned bits)
{
    return cnt_even(bits);
}

/* Swap two values */
void swap(long *xp, long *yp) {
    long t0 = *xp;
    long t1 = *yp;
    *xp = t1;
    *yp = t0;
}

/* Swap, using local array */
void swap_a(long *xp, long *yp) {
    volatile long loc[2];
    loc[0] = *xp;
    loc[1] = *yp;
    *xp = loc[1];
    *yp = loc[0];
}

/* Swap elements i & i+1 in array a */
void swap_ele(long a[], int i)
{
    swap(&a[i], &a[i+1]);
}

long scount = 0;
/* Swap elements i & i+1 in array a */
void swap_ele_se(long a[], int i)
{
    swap(&a[i], &a[i+1]);
    scount++;
}

long sum = 0;
/* Swap elements i & i+1 in array a */
void swap_ele_su(long a[], int i)
{
    swap(&a[i], &a[i+1]);
    sum += a[i];
}



long flip(long x)
{
    if (x >= 0)
	return x;
    else
	return flip(-x) * x;
}

#if 0
long flip(long x)
{
    if (x ______)
	return ____;
    else
	return flip(_____) * _____;
}
#endif

int main(int argc, char *argv[])
{
    long *ap = calloc(sizeof(long), argc-1);
    long val = 1L;
    long cval;
    int i;
    int cnt = argc-1;
    for (i = 0; i < cnt; i++) {
	ap[i] = strtol(argv[i+1], NULL, 0);
    }
    if (cnt == 2)
	val = mul_2p1(ap[0], ap[1])-1;
    else if (cnt == 3)
	val = mul_3(ap[0], ap[1], ap[2]);
    else
	val = mul_list(ap, cnt);

    printf("Prod [ ");
    for (i = 0; i < cnt; i++) {
	ap[i] = strtol(argv[i+1], NULL, 0);
	printf("%ld ", ap[i]);
    }
    printf("] = %ld\n", val);
    cval = mul_list_r0(ap, cnt);
    if (val != cval) {
	printf("Oops.  mul_list_r0 returns %ld\n", cval);
    }
    cval = mul_list_r1(ap, cnt);
    if (val != cval) {
	printf("Oops.  mul_list_r1 returns %ld\n", cval);
    }
    cval = mul_list_r3(ap, cnt);
    if (val != cval) {
	printf("Oops.  mul_list_r3 returns %ld\n", cval);
    }
    /* Do this one last, since it's destructive */
    cval = mul_list_r2(ap, cnt);
    if (val != cval) {
	printf("Oops.  mul_list_r2 returns %ld\n", cval);
    }
    return 0;
}