RECURSION AUGMENTED FLOWCHART SCHEMES

In a previous section, we have shown that recursion schemes are more powerful than flowchart schemes. Now we add to the basic model of flowchart of program schemes a mechanism resembling recursive procedures and calls as defined in PL/I, for example. We find that such recursion augmented flowchart schemes are in fact equivalent in expressive power to recursion schemes. Thus we show that recursion schemes are indeed one version of the model we seek to study the power of programs when augmented by recursion, in contrast to programs without this extension tut perhaps with other additions. 

Let P be a recursion augmented flowchart scheme. Show that if P is a macroexpansion of P, then P is strongly equivalent to P (Corollary 7.14). Give an algorithm for performing a complete first level mcroexpan-sion of P. ... 

Recursion schemes are equivalent to procedure augmented flowchart schemes. 

Every recursion scheme can be translated into a flowchart scheme augmented by one pushdown store. 

In this chapter we start the discussion of an alternative model for programs, designed to reflect recursive properties of programming languages. We shall see that this model does indeed represent an augmentation of the flowchart model we have been studying up to now. One topic of concern will be when recursion equations can be translated into flowchart form - when recursion schemes are flowchartable. 

---