fac-tail-recursion.c

// This is a demo of how tail recursion could be implemented, logically
// speaking.
//
// Most C compilers will actually optimize the following code into true
// tail-recursive code (try it at http://llvm.org/demo/ ):
//
//   long factorial(long n) {
//     if (n == 0) return 1;
//     return n * factorial(n - 1);
//   }
//
#include <stdio.h>
#include <stdlib.h>

// simple trampoline
typedef void *(*continuation_t)(void);
void trampoline(continuation_t f) {
  while ( (f = (continuation_t)f()) ) {  }
}

// registers
long in0 = 0;
long in1 = 0;
long out0 = 0;

// factorial is:
//  input: integer n such that n >= 0
//  output: [n × (n-1) × (n-2) × … × 1]

// Our factorial implementation:
//
// fun factorial (n, x:1) {
//   if n == 0:
//     x
//   else:
//     factorial(n - 1, x * n)
// }
//
// fun factorial (n, x:1)
void *factorial() {
  printf("factorial(%ld, %ld) -> ", in0, in1);
  // if n == 0:
  if (in0 == 0) {
    // x
    out0 = in1;
    return NULL;
  // else:
  } else {
    // factorial(n - 1, x * n)
    in1 = in1 * in0;
    in0 = in0 - 1;
    return (void*)&factorial;
  }
}

// Here we trust the compiler to optimize this into a tail-recursive call
long factorial2(long n) {
  printf("factorial2(%ld) -> ", n);
  if (n == 0) return 1;
  return n * factorial2(n - 1);
}

int main(int argc, const char * argv[]) {
  // print factorial(10, 1)
  in0 = 10; in1 = 1;
  trampoline(&factorial);
  printf("%ld -- %s\n", out0, out0 == 3628800 ? "OK" : "FAIL");
  // Output: factorial(10, 1) -> factorial(9, 10) -> factorial(8, 90) ->\
  //  factorial(7, 720) -> factorial(6, 5040) -> factorial(5, 30240) ->\
  //  factorial(4, 151200) -> factorial(3, 604800) -> factorial(2, 1814400) ->\
  //  factorial(1, 3628800) -> factorial(0, 3628800) ->\
  //  3628800 -- OK
  
  printf("\n");
  out0 = factorial2(10);
  printf("%ld -- %s\n", out0, out0 == 3628800 ? "OK" : "FAIL");
  // Output: factorial2(10) -> factorial2(9) -> factorial2(8) ->\
  //  factorial2(7) -> factorial2(6) -> factorial2(5) -> factorial2(4) ->\
  //  factorial2(3) -> factorial2(2) -> factorial2(1) -> factorial2(0) ->\
  //  3628800 -- OK
  
  return 0;
}