#include <stdio.h>

/** **********************************************************************
 * pure, naive, recursive version
 ** **********************************************************************/
int sum1(int val,int count)
{
    int s;
    
    if (count <= 0) {
        // nothing left
        s = 0;
    }
    else {
        // add one instance of 'val' to the result
        // of calling sum1 with one less count
        s = val + sum1(val,count-1);
    }
    
    return s;
}
/** **********************************************************************
 * recursive version transformed with 'tail recursion modulo cons'
 ** **********************************************************************/
// set up a pure tail recursive constructor
int sum2_cons(int val,int count,int *accumulator)
{
    // quit if no counts left
    // important to quit here. not allowed to quit at the end
    // and if you don't quit you'll get a segfault when the stack overflows
    if (count <= 0) return 0;
    
    // sum into the accumlator. remember, the accumulator can be anything that
    // holds the intermediate state of whatever you are constructing
    *accumulator += val;
    
    // call back into itself.
    // now we have tail recursion. nothing happens after
    // the recursive call. the recursion will still
    // end when the count argument goes to 0
    sum2_cons(val,count-1,accumulator);
}


// original function is changed to a stub that calls
// the pure tail recursive version 
// has the pure tail recursion
int sum2(int val,int count)
{
    // set up an accumulator 'x' which will hold the
    // intermediate results
    int x = 0;
    
    // call the stub, passing it the original parameters
    // plus a pointer to the accumulator
    sum2_cons(val,count,&x);
    
    // return the value of x
    return x;
}

/** **********************************************************************
 *  change the constructor to be iterative
 ** **********************************************************************/
// set up an iterative constructor
int sum3_cons(int val,int count,int *accumulator)
{
    LOOP:
    
    // quit if no counts left
    // important to quit here. not allowed to quit at the end
    // and if you don't quit you'll get an infinite loop instead of a segfault
    if (count <= 0) return 0;
    
    // sum into the accumlator. remember, the accumulator can be anything that
    // holds the intermediate state of whatever you are constructing
    *accumulator += val;
    
    // now, instead of the recursive call back into itself,
    // change the arguments as required to make them the same value they would
    // have been in the recursive call, and jump back to the beginning
    count--;
    goto LOOP;  // yes yes a goto is considered harmful, but this is a good use of it
}

// original stub, same as sum2
int sum3(int val,int count)
{
    // set up an accumulator 'x' which will hold the
    // intermediate results
    int x = 0;
    
    // call the stub, passing it the original parameters
    // plus a pointer to the accumulator
    sum3_cons(val,count,&x);
    
    // return the value of x
    return x;
}

/** **********************************************************************
 *  for the purists, get rid of the goto
 ** **********************************************************************/
// set up an iterative constructor without the hideous GOTO
int sum4_cons(int val,int count,int *accumulator)
{
    // quit if no counts left
    // if you don't quit you'll get an infinite loop instead of a segfault
    while(count > 0)  {
        // sum into the accumlator. remember, the accumulator can be anything that
        // holds the intermediate state of whatever you are constructing
        *accumulator += val;
        
        // now, instead of the recursive call back into itself,
        // change the arguments as required and jump back to the beginning
        count--;
    }
    
    return 0;
}

// original stub, same as sum2 and sum3
int sum4(int val,int count)
{
    // set up an accumulator 'x' which will hold the
    // intermediate results
    int x = 0;
    
    // call the stub, passing it the original parameters
    // plus a pointer to the accumulator
    sum4_cons(val,count,&x);
    
    // return the value of x
    return x;
}

/** **********************************************************************
 *  simple test fixture
 ** **********************************************************************/
int main(int argc,char *argv[])
{
    int a;
    int b;
    int c;
    int d;
    
    // test with positive count value, should return 5
    a = sum1(1,5);
    b = sum2(1,5);
    c = sum3(1,5);
    d = sum4(1,5);
    
    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);

    // better check it with 0, should return 0
    a = sum1(1,0);
    b = sum2(1,0);
    c = sum3(1,0);
    d = sum4(1,0);
    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
    
    // negative numbers return a 0 by specification. 
    // that is why the termination condition is 'count <= 0' instead of 
    // 'count == 0'
    a = sum1(1,0);
    b = sum2(1,0);
    c = sum3(1,0);
    d = sum4(1,0);
    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
    return 0;
}