/*   How to Replace Loops with Tail Recursion

In mathematics, all computer programs are recursive functions (totally
recursive for the ones that terminate).  For- and while loops are
equivalent to simplified forms of recursion.  A function is
tail-recursive if nothing else is done after any recursive call (but
be sure to read expressions inside out: n*f(n-1) does not call f last,
it multiplies last)

An optimizing compiler can also recognize these cases of recursion and
compile them to efficiently excuting code where recursive calls do not
push new frames onto the runtime call stack.  The gcc/g++ compilers
can do this at certain optimizaion levels (use gcc -O2). But
Functional languages such F# do this best.  Beware, however, that
Java, Python, C# and most object-oriented languages do NOT optimize
tail recursion.  One reason for this is that it becomes harder to
implement it along with dynamic dispatch, where the version of the
function being called is not determined at compile time.

The functional style of programming is becoming more important as it's
naturally stateless.  There will be situations where recursion is more
natural to use than loops, and so it is important to understand the
difference between good and bad ways to use recursion.  Tail recursive
programs are always equivalent to loops.

This program in C shows you how to convert a program that uses while
loops into a tail-recursive program.

The basic idea is the following:

*** For every variable that might be assigned to a new value in a
while loop, add a new argument (parameter) to the function.  The
initial values of the function are the values passed to these
arguments when the function is initially called.  The function's body
should first test if the boolean condition of the while loop is still
true before proceeding: if it's false it should execute the code that
comes after the loop. If the boolean is true it should execute the
body of the while loop and end with a recursive call to itself, with
new values for the parameters that changed inside the loop.
***
*/

#include<stdio.h>

// first example: function to calculate n!:
int fact1(int n) {
  int ax = 1; // accumulator
  while (n>1) {
      ax = ax * n;
      n -= 1;
    }
  return ax;
}
// can be rewritten tail-recursively as
int fact(int n, int ax) {
  if (n>1) {
      return fact(n-1, ax*n);
    }
  else return ax;
}
// The function must be called with initial value 1 for ax.  C compilers
// will generate nearly identical code for the two functions.
// In this example, the entire body of the while loop is replaced by a
// tail recursive call.  The result of the call is immediately returned by
// the function, so it is tail recursive.   Compare this to the non-tail
// recursive version of n!:

int fact2(int n) { if (n<2) return 1; else return n*fact2(n-1); }

// This function is not tail-recursive because the last operation is
// NOT the recursive call but the mulitplication operation *.  In the
// tail-recursive version, the * was moved INSIDE the recursive call:
// fact(n-1,ax*n).  Since C, like most languages, is call-by-value, this
// means that ax*n is evaluated before the recursive call.

// Next example: function to calculate nth fibonacci number:

int fibw(int n) {
  int a =1, b = 1;
  while (n > 2) {
      b = a+b;
      a = b-a;  // a will have b's original value
      n--;
    }
  return b;
}

// This can be rewritten as the following tail recursive function.  Since
// we want to encapsulate the intial values that should be passed into this
// function, we will define it as a function inside another function.
// Nested functions are allowed in Gnu C (but not in ANSI C). All functional
// programming languages will allow it.

int fib(int n) {
  int tfib(int n, int a, int b)  {  // inner function of fib
    if (n<=2) return b;
    else return tfib(n-1, b, a+b);
  }
  return tfib(n,1,1);  // body of outer "public" function
}//fib

// Compare this to the infamous "fib(n-1) + fib(n-2)" implementation, where
// neither recursive call is a tail-call because the last operation to
// be performed is the addition +.  Notice that in the tail-recursive function
// above, the + has once again been moved inside the call, as an argument
// that's evaluated first.  This is a common characteristic of tail-recursive
// functions.

// Function to calcuate the greatest common divisor of two integers:

int gcd1(int a, int b) {
  while (a!=0) {
      int tmp = a;
      a = b % a;
      b = tmp;  // b becomes original value of a
    }
  return b;
}
// tail recursively:

int gcd(int a, int b) {
  if (a==0) return b; else return gcd(b%a,a); 
}

// Note that in this function, the only use of the tmp variable was to
// help preserve the original value of a before it was changed, because
// C does not allow simulataneous assignments (a,b=...).  But with the
// tail recursive call, that's in fact what we're doing.  Thus in the
// recursive version tmp is not needed.


// Calcuate m**n in log(n) steps by binary factorization of n:
// m**13 = m * m**4 * m**8.

int expt1(int m, int n) {
  int factor = m;   // **binary factor of m
  int ax = 1;       // accumulator, default m**0
  while (n>0) {
    if (n%2==1)  {
      ax = ax*factor;
    }
    factor = factor*factor; // m, m**2, m**4, m**8, etc..
    n = n/2;
  }
  return ax;
}

// tail recursively: here it looks a bit more different.  The while
// loop always changes the factor and n variables, but may not change
// ax depending on the condition.  Thus you should have an if statement
// that makes one of two recursive calls, both calls must be tail calls.
int expt(int m, int n) {
  int iter(int n, int ax, int factor) {
    if (n<1) return ax;
    else if (n%2==1) return iter(n/2, ax*factor,factor*factor);
    else return iter(n/2,ax,factor*factor);
  }
  return iter(n,1,m);
}
// Notice that the inner tail-recursive function does not require m as 
// an argument, because it does not change.  m is a free variable in the
// inner iter function.  This is OK in C because the lifetime of m (on the
// stack) is the same as the lifetime of the closure itself.  Unlike the
// example of the K combinator, lambda x.return (lambda y.x); we are not
// returning the closure, which won't work in C.


// The last example takes a function pointer as an argument and applies 
// it to an array of integers.

typedef int (*operation)(int,int);  // type (int,int) -> int

// Let's first look at a version of the function that's NOT tail-recursive:

int reduce1(int A[], int length, operation op, int id) {
  if (length<1) return id; 
  else return op(reduce1(A, length-1, op, id), A[length-1]);
}

// Given int A[] = {2,4,6,8}, and int add(int x, int y) {return x+y;}, 
// calling reduce1(A,4,add,0) will return 20, the sum of the values in 
// the array.  The id argument is the "identity" of the operation, and
// is the default value when the array is empty.  The function will in
// fact calculate (((0+2)+4)+6)+8: the operation op is assumed to be
// LEFT-associative.
// This function is not tail-recursive because the recursive call is made
// inside the call to op: the last operation of the function is to call op.
// To write a tail-recursive version, we should try to move the call to op
// inside the recursive call instead.  

int reduce(int A[], int length, operation op, int id) {
  int inner(int A[], int length, int ax) {
    if (length<1) return ax; else return inner(A+1, length-1, op(ax,A[0]));
  }//inner
  return inner(A,length,id);
}
// Note that C allows pointer arithmetic: since A is a pointer, A+1 will 
// point to the array without the first element.  This function is 
// consistent with reduce1 because it also assumes that the operation is 
// left-associative.  In main() below the solution is tested on the minus
// operation, which is not naturally associative.

// This time, we write the non-recurisve version after the tail-recursive one:
int reduce2(int A[], int length, operation op, int ax) {
  while (length>0) {
    ax = op(ax,A[0]); // apply op to accumulator ax and first element of A
    A++;  // advance pointer A to point to next element
    length--; // A now points to an array of shorter length
  }
  return ax;
}

// The following NON-tail recursive version, however, assumes that the
// operation is RIGHT-associative.  It's not equivalent to reduce.

int fold(int A[], int length, operation op, int id) {
  if (length<1) return id; else return op(A[0], fold(A+1,length-1,op,id));
}

// CHALLENGE: write a tail-recursive version of fold.  

int main()
{
  printf("%d %d %d %d\n", fact(5,1), fib(10), gcd(8,12), expt(2,13));
  int minus(int a, int b) { return a-b; } // minus is not associative
  int A[] = {8,5,3,1};
  printf("reduce1: %d\n", reduce1(A+1,3,minus,A[0])); // ((8-5)-3)-1 = -1
  printf("reduce2: %d\n", reduce2(A+1,3,minus,A[0])); // also -1
  printf("reduce: %d\n", reduce(A+1,3,minus,A[0]));   // also -1
  printf("fold: %d\n", fold(A,4,minus,0)); // 8-(5-(3-(1-0))) = 5

  return 0;
}

// compile with -O2 optimization.

// Trick question before you leave: is the following function tail-recursive?

int find(int x, int A[], int length) { // determine if x is found in A
  return (length>0) && (x==A[0] || find(x,A+1,length-1));
}

/*
The answer is complicated: it SHOULD be tail recursive because the boolean
operators || and && are short-circuited.  This means that the above code
is equivalent to:

   if (length<1) return 0;
   else if (x==A[0]) return 1;
   else return find(x,A+1,length-1);

which is clearly tail-recursive.  However, your version of the C compiler
may not recognize this fact, and will not optimize away the recursion.  In
a truly functional programming language such as F#, we can expect such
cases to also be optimized.
*/