The interesting thing about this solution is that it uses an internal function that does the recursion. The result of the recursion is stored as an argument. When a special case is hit (such as the list being empty in our example), the result of the recursion is returned.
The recursion is tail recursion. It means that whenever we recurse, we ensure that the last function that is evaluated is exactly the same function that we are defining. In our example, we always called reverse' function as a top expression. The compiler optimizes the tail recursive functions such that they are executed in constant space and without adding them to stack.
The following diagram shows how a tail recursive function works. The diagram shows how a tail recursive reverse' function works. You can see that at each step, the recursion does the same operation till it reaches a point where recursion can be stopped. Since each operation in a tail recursion is same, the compiler can run recursion without incurring an overhead on stack. Please refer to the following diagram:
The following snippet to calculate the length of a list will highlight this fact:
- Implementation without tail recursion:
length [] = 0
length (_:xs) = 1 + length xs
- Implementation with tail recursion:
length xs = length' xs 0
where
length' [] len = len
length' (_:xs) len = length' xs (1+len)