Recursive function calls may be treated by the programming language like any other function calls. This will require the allocation of an additional stack frame for each call. Therefore recursive calls may cause a stack overflow. Furthermore this overhead of stack management returns in longer execution times compared with a loop.

Functional programming languages like F# will use recursion in many cases. Therefore they handle such function calls in a more efficient way. For example the compiler can turn recursive function calls into loops.

But also the software developer itself has several possibilities to increase the efficiency of his functions. One important possibility is called „tail recursion“. Tail recursive function calls can be invoked without the need to extend the call stack. This is possible because an already created call frame can be reused. Therefore such tail calls are really fast and they will not result in stack overflows at runtime. Furthermore in many cases the compiler can turn tail recursive function calls into loops.

 
Tail recursion

So it is important to understand how to write tail recursive functions. There is an easy rule: The recursive function call must be in a tail position.

The following list shows definitions for tail positions:

• The body of a function or the last expression in a function
• The body of an if branch, where the conditional expression is in tail position
• The body of a pattern matching, where the match expression is in tail position
• The body of a let binding, where the binding expression is in tail position

One restriction to the previous definitions is, tail calls cannot be performed in try-catch or try-finally blocks.

 
Example

To show the difference of a recursive and a tail recursive function call we will use a simple example. A function should be implemented, which calculates the sum of all values from 1 to x. For example a function call with x=5 should calculate the sum 1+2+3+4+5 which is 15.

The following source code shows a possible implementation of this function.

let rec executeRecursive x = 
    if x = 1
    then 1
    else x + executeRecursive (x-1)

The call of executeRecursive is not on a tail position. After the function call returns the return value will be added to x. Therefore the last expression of the function is „x + <return value of function call>“.

This function will therefore increase the call stack with each recursive call. You may test this by using a large value for x. For example on execution of the function with x = 1000000 I get a StackOverflowException.

But with a little modification it is possible to create a tail recursive function call. The following source code shows the modified example. An additional internal function was created. This internal function is used to hide implementation details like the changed parameters. The actual sum is used as additional parameter. With this change the „x + …“ expression is moved and therefore it is executed prior to the function call. This change moves the function call in a tail position.

let executeTailRecursive x = 
    let rec executeTailRecursiveInternal x total = 
        if x = 0
        then total
        else executeTailRecursiveInternal (x-1) (total+x)
    executeTailRecursiveInternal x 0

 
If you try to execute this modified function with a large parameter, e.g. x = 1000000, the StackOverflowException will not occur. The new function is tail recursive and therefore the stack frame is reused on every recursive call. Or maybe the compiler has transferred the function into a loop.

 
Summary
Tail recursive functions will increase the execution speed of recursive function calls and prevent stack overflow exceptions. Of course they are not always needed. If you have function calls with only a view recursive calls, you don’t need this code optimization. But if an optimization is needed, tail recursion will offer a way to improve the efficiency of your applications.