This sophisticated technique of arranging recursion allows you to avoid stack consumption by putting all function calls into the tail position with continuation, that is, a function that performs the remaining computations instead of returning result to the caller. Let me demonstrate this technique by refactoring the factorial implementation one more time as shown in the following snippet (Ch7_6.fsx
):
let rec ``factorial (cps)`` cont = function | z when z = 0I -> cont 1I | n -> ``factorial (cps)`` (fun x -> cont(n * x)) (n - 1I)
Although slightly mind-bending, the code consists of all tail calls:
``factorial (cps)``
is a tail callcont
The cont
function has inferred signature of (BigInteger -> 'a);
so, in order to perform the sought-for calculations, using the id
identity function for the cont
as the first argument of ``factorial (cps)``
would be just fine. Testing the continuation passing style implementation of ``factorial (cps)``
function in FSI is presented in the following screenshot:
This works perfectly, although those of you not already familiar with continuation passing style may develop a headache when dealing with this code for the first time.