By moving the recursive call to tail position we can transform a recursive algorithm into an iterative one.
For example, let's define a naive factorial function:
fact n =
if n <= 1 then
1
else
n * fact (n - 1)
This definition if very straight-forward. To calculate the factorial of some number n, it checks: if n is less than or equal to 1, if so returns 1, otherwise multiply it with the result of factorial of n - 1.
The evaluation of this program will follow like so:
fact 4 4 * fact 3 4 * 3 * fact 2 4 * 3 * 2 * fact 1 4 * 3 * 2 * 1 12 * 2 * 1 24 * 1 24
Notice that this expression can only be evaluated once every term is known.
Until them we must keep expanding the computation.
Let's contrast this if this other definition of factorial:
fact acc n =
if n <= 1 then
acc
else
fact (acc * n) (n - 1)
This definition is a bit trickier to understand.
The first difference is that we have two parameters instead of one, one for accumulating the result and one being the nth factorial number we want to calculate.
It then checks: If n is less than or equal to 1, if so return the accumulator, otherwise, call the function again, passing the accumulator multiplied by n and n - 1.
The evaluation of this program will follow like so:
fact 1 4 fact 4 3 fact 12 2 fact 24 1 24
Notice that unlike the previous definition of factorial, this one doesn't need to wait until every term in known.
Instead of building this ever-expanding multiplication expression it carries that result in its arguments as the accumulator.
Even though both are recursive definitions, the shape of their evaluation is very different, both in time and space.