Pseudo-recursive procedures (Q1057638)

Based on a decidable notion of recursivity of procedures (or functions) in ALGOL-like programs we define pseudo-recursive procedures to be those that do not need an activation record of their own on the runtime stack; their storage can be allocated within the activation record of a strictly-recursive (i.e. not pseudo-recursive) dynamic predecessor. We present an algorithm that characterizes each procedure of a program as being either non-recursive, pseudo-recursive or strictly-recursive and associates each pseudo-recursive procedure with one appropriate strictly- recursive one. With this information a better suited implementation technique can be chosen for each type of procedure.