FACTORISATION OF THE FACTORIAL AN EXAMPLE OF INVERTING THE FLOW OF COMPUTATION

Abstract

As an example of the transformational programming method, a previously unknown algo- rithm for calculating factorials is derived. The derivation is done by the unfold-fold strat- egy with transformation rules for changing the recursion structure of functions. These transformation rules (inverting the flow of computation and splitting recursion) are pre- sented and explained. The derivation proceeds from a system of linear recursive functions, via tail-recursive functions, to an efficient imperative program. The resulting program is, in our opinion, only intelligible by way of its derivation. It is also shown how a similar derivation leads to a version of the algorithm that may be executed on 2 processors.