D - Transformations that remove recursion

Summary

The specification of functions and processes by means of pre-conditions and post-conditions requires that any repetitive or accumulative aspects of the computation must be indicated by recursion. Now, although many modern procedural programming languages support recursion and hence allow programming in a functional style, the run-time overhead of large amounts of stack manipulation imposed by the related control mechanism is unacceptable in certain applications.

Throughout this book, our central premise has been that to make best use of programmer efforts we should concentrate on correctness and ignore run-time efficiency considerations. Of course, to spend much time and effort developing a correct program only to have its correctness violated by the introduction of some slick trick which substantially reduces execution time – but does not quite always work – is to invalidate the whole exercise. Consequently all such transformations and optimisations must also be proven correct and, if appropriate, programmed into the system so as to protect them from human error.

As noted in Chapter 9 we already trust hardware extensions to the minimal set of arithmetic functions which, for instance, compute integer sums and products without recursive recourse to the increment and decrement instructions. On the software side, we showed in Chapter 7 how certain dataflow charts can be unwound into iterative control flowcharts.

The recursion-to-iteration transformation given in Chapter 7 is particularly useful in that it is widely applicable.