Lately, I’ve been adding support for tail recursion optimization in the Blaise compiler. Anytime the last statement inside of the body of a function is a call to itself: it’s a tail recursive call. The execution moves from the bottom of the body of code to the top of the body of code. This works just like a loop. Normally with recursion the computer will push an environment onto stack memory and move into the new recursive function call with a free environment to which it can write local variables. With tail recursion it’s not necessary to push onto stack memory. The code can be transformed into a loop and the Blaise compiler does just that. Check out the example below.

Here is a tail recursive function

let someFunction arg1 arg2 =
    (* body of function *)
    (* The last statement is a recursive call.*)
    someFunction arg1' arg2'
;;

When the example function above is compiled to C we can use ‘goto’ statements to turn the function into a loop.

void * someFunction(void * arg1, void * arg2) {
someFunction_goto:
    /* body of function */
    /*
        The recursive call is turned into variable reassignments and
        a goto statement that takes us to the top of the loop
    */
    arg1 = arg1';
    arg2 = arg2';
    goto someFunction_goto;
}

Next I plan on adding tail recursion support for mutually (tail) recursive functions.