Loops and Tail Recursion

Loops and Tail Recursion

There is an equivalence between loops and tail recursive functions. Let's revisit the simple counting loop example from before:

This loop can be implemented using a feature that performs a tail recursive call as follows

Tail recursion means that a feature performs no more code after a recursive call to itself. For the compiler, this means that there is no need to create a new stack frame for the call. Instead, the current stack frame can be reused, new values can be assigned to the argument fields and the call can be implemented by a simple branch to the beginning of the code of the feature.

The Fuzion intermediate language represents loops using tail recursion. The code generator back ends guarantee to optimize tail recursive calls as described here.

This has two important consequences: First, for the developer, code can be written using loops or tail recursive functions. There is no performance benefit using one over the other. Second, analysis tools become simpler, there is no need for loop analysis, it is sufficient to support analysis of recursion (which is what those adept at static analysis tend to prefer).