# tail recursion / tail call

The technique of writing a function so that recursive calls are only done immediately before function return, particularly when recursive control structures are used in place of iterative ones. — Wiktionary: Tail Recursion

As I reworked the blog posts on Lua and Swift (Lua and Swift in iOS, Factorial calculation with Lua and Swift, Recursive calls between Lua and Swift), I took a closer look at the ;`factorial` function I use. I asked myself: Can Lua tail recursion?

## Tail recursion

Usually a method call writes the result to the stack. In a recursive call, this means that several data items accumulate on the stack. Only after the last call has been made the calling method processes the individual results. This can cause a Stack overflow if the stack provided for this purpose does not have enough memory.

If a programming language or much more the compiler supports tail recursion then the recursive function is not called with a `call`. Instead, it simply jumps (`jump`) directly to the function. This means that the called method does not have to write anything to the stack.

## Factorial as tail recursion

To call a method call tail recursive, the method call must be the last command. Nothing may follow after that.

If you look at the following Factorial example from the blog post Factorial calculation with Lua and Swift, the `factorial` call is at the end. But it can also be swapped with the `n` within the multiplication. In fact the multiplication is the last call and not the recursive call.

``````function factorial(n)
if (n == 0) then
return 1
else
return n * factorial(n - 1)  -- not tail recursive
end
end
``````

To construct a tail recursive call, the multiplication must be done first. The result is passed with the method call. To make this possible, the recursive function has two parameters. The counter, which is reduced by 1 with each call, and a second parameter to store the subtotal.

``````function fact_(n, acc)
if (n == 0) then
return acc
else
return fact_(n - 1, n * acc)
end
end
``````

The reduction of the counter as well as the multiplication is now done before. The result is passed to the `acc` parameter. This parameter works like an Accumulator within a CPU: “the accumulator is a register in which intermediate arithmetic and logic results are stored”.

## Result

If you call the `factorial` method with 1 million, a stack overflow occurs:

``````> print(factorial(1000000))
stdin:5: stack overflow
stack traceback:
stdin:5: in function 'factorial'
...
stdin:5: in function 'factorial'
stdin:1: in main chunk
[C]: in ?
``````

The tail recursive method `fact_`, on the other hand, has no error and returns inf. The result is infinity after 170 iterations.

``````> print(fact_(1000000, 1))
inf
``````

Lua is just one example of a language that supports tail recursion. The classic functional programming languages like Scheme and LISP also have tail recursion. So do the JVM-based languages Clojure and Scala, but they handle tail recursion separately because the Java compiler does not support it. C, C++ and Objective-C can be optimized by the compiler (depending on the compiler). What about Swift?

## Swift and tail recursion

I’m not the first person asking that question. On Stack Overflow there is this question: Does Swift implement tail call optimization?

I wrote the factorial methode in Swift:

``````func factorial(n: Int, acc: Double) -> Double {
if n <= 0 {
return acc
} else {
return factorial(n: n - 1, acc: acc * Double(n))
}
}
``````

Compiling the code with the Swift compiler and outputting it as an assembly creates 3 `callq` calls that grep finds:

``````> swiftc -emit-assembly factorial.swift | grep -i call
callq _memset
callq _memset
callq _\$s9factorialAA1n3accSdSi_SdtF
``````

With the -O parameter (see Enabling Optimizations) on the other hand, the code is optimized. In this case, the compiler generates code without `callq` calls:

``````> swiftc -O -S factorial.swift | grep -i call
``````

### Calling the factorial function

Add the following code to call and output the factorial function with 1 million:

``````print(factorial(n: 1000000, acc: 1))
``````

If you run the Swift code on the command line without optimization, the `callq` calls within the factorial method will cause an error:

``````❯ swift factorial.swift
    31980 illegal hardware instruction  swift factorial.swift
``````

When running with optimization (-O parameter) the application runs without errors and outputs inf. The calculated value is too large and is therefore infinitive.

``````❯ swift -O factorial.swift
inf
``````

### LLVM - Tail call optimization

Swift uses LLVM as compiler, which has a Tail call optimization.

## Summary

Tail recursion is a way to walk recursively through lists and graphs and not run into the risk of a stack overflow.