1:#include <stdio.h>
   2:
   3:/** **********************************************************************
   4: * pure, naive, recursive version
   5: ** **********************************************************************/
   6:int sum1(int val,int count)
   7:{
   8:    int s;
   9:    
  10:    if (count <= 0) {
  11:        // nothing left
  12:        s = 0;
  13:    }
  14:    else {
  15:        // add one instance of 'val' to the result
  16:        // of calling sum1 with one less count
  17:        s = val + sum1(val,count-1);
  18:    }
  19:    
  20:    return s;
  21:}
  22:/** **********************************************************************
  23: * recursive version transformed with 'tail recursion modulo cons'
  24: ** **********************************************************************/
  25:// set up a pure tail recursive constructor
  26:int sum2_cons(int val,int count,int *accumulator)
  27:{
  28:    // quit if no counts left
  29:    // important to quit here. not allowed to quit at the end
  30:    // and if you don't quit you'll get a segfault when the stack overflows
  31:    if (count <= 0) return 0;
  32:    
  33:    // sum into the accumlator. remember, the accumulator can be anything that
  34:    // holds the intermediate state of whatever you are constructing
  35:    *accumulator += val;
  36:    
  37:    // call back into itself.
  38:    // now we have tail recursion. nothing happens after
  39:    // the recursive call. the recursion will still
  40:    // end when the count argument goes to 0
  41:    sum2_cons(val,count-1,accumulator);
  42:}
  43:
  44:
  45:// original function is changed to a stub that calls
  46:// the pure tail recursive version 
  47:// has the pure tail recursion
  48:int sum2(int val,int count)
  49:{
  50:    // set up an accumulator 'x' which will hold the
  51:    // intermediate results
  52:    int x = 0;
  53:    
  54:    // call the stub, passing it the original parameters
  55:    // plus a pointer to the accumulator
  56:    sum2_cons(val,count,&x);
  57:    
  58:    // return the value of x
  59:    return x;
  60:}
  61:
  62:/** **********************************************************************
  63: *  change the constructor to be iterative
  64: ** **********************************************************************/
  65:// set up an iterative constructor
  66:int sum3_cons(int val,int count,int *accumulator)
  67:{
  68:    LOOP:
  69:    
  70:    // quit if no counts left
  71:    // important to quit here. not allowed to quit at the end
  72:    // and if you don't quit you'll get an infinite loop instead of a segfault
  73:    if (count <= 0) return 0;
  74:    
  75:    // sum into the accumlator. remember, the accumulator can be anything that
  76:    // holds the intermediate state of whatever you are constructing
  77:    *accumulator += val;
  78:    
  79:    // now, instead of the recursive call back into itself,
  80:    // change the arguments as required to make them the same value they would
  81:    // have been in the recursive call, and jump back to the beginning
  82:    count--;
  83:    goto LOOP;  // yes yes a goto is considered harmful, but this is a good use of it
  84:}
  85:
  86:// original stub, same as sum2
  87:int sum3(int val,int count)
  88:{
  89:    // set up an accumulator 'x' which will hold the
  90:    // intermediate results
  91:    int x = 0;
  92:    
  93:    // call the stub, passing it the original parameters
  94:    // plus a pointer to the accumulator
  95:    sum3_cons(val,count,&x);
  96:    
  97:    // return the value of x
  98:    return x;
  99:}
 100:
 101:/** **********************************************************************
 102: *  for the purists, get rid of the goto
 103: ** **********************************************************************/
 104:// set up an iterative constructor without the hideous GOTO
 105:int sum4_cons(int val,int count,int *accumulator)
 106:{
 107:    // quit if no counts left
 108:    // if you don't quit you'll get an infinite loop instead of a segfault
 109:    while(count > 0)  {
 110:        // sum into the accumlator. remember, the accumulator can be anything that
 111:        // holds the intermediate state of whatever you are constructing
 112:        *accumulator += val;
 113:        
 114:        // now, instead of the recursive call back into itself,
 115:        // change the arguments as required and jump back to the beginning
 116:        count--;
 117:    }
 118:    
 119:    return 0;
 120:}
 121:
 122:// original stub, same as sum2 and sum3
 123:int sum4(int val,int count)
 124:{
 125:    // set up an accumulator 'x' which will hold the
 126:    // intermediate results
 127:    int x = 0;
 128:    
 129:    // call the stub, passing it the original parameters
 130:    // plus a pointer to the accumulator
 131:    sum4_cons(val,count,&x);
 132:    
 133:    // return the value of x
 134:    return x;
 135:}
 136:
 137:/** **********************************************************************
 138: *  simple test fixture
 139: ** **********************************************************************/
 140:int main(int argc,char *argv[])
 141:{
 142:    int a;
 143:    int b;
 144:    int c;
 145:    int d;
 146:    
 147:    // test with positive count value, should return 5
 148:    a = sum1(1,5);
 149:    b = sum2(1,5);
 150:    c = sum3(1,5);
 151:    d = sum4(1,5);
 152:    
 153:    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
 154:
 155:    // better check it with 0, should return 0
 156:    a = sum1(1,0);
 157:    b = sum2(1,0);
 158:    c = sum3(1,0);
 159:    d = sum4(1,0);
 160:    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
 161:    
 162:    // negative numbers return a 0 by specification. 
 163:    // that is why the termination condition is 'count <= 0' instead of 
 164:    // 'count == 0'
 165:    a = sum1(1,0);
 166:    b = sum2(1,0);
 167:    c = sum3(1,0);
 168:    d = sum4(1,0);
 169:    printf("a=%d b=%d c=%d d=%d\n",a,b,c,d);
 170:    return 0;
 171:}
 172: