Inline expansion replaces a call to a procedure with the procedure’s body. Inline expansion, among other benefits, eliminates procedure call overhead and improves addressing locality. Recursion presents a problem, since a recursive call has an infinite inline expansion. In direct recursion, a procedure contains a call to itself; in indirect recursion, procedure A calls procedure B which (calls procedure C which…) calls procedure A. Direct recursion is preferred over indirect recursion because direct recursion is simpler to eliminate or simulate, and some program analyses can handle only direct recursion.

The authors develop a nontrivial condition indicating when it is possible to convert indirect recursion to direct recursion, and give an algorithm for the conversion. They examine the interactions between expansion and tail-call elimination and show that the special case of indirect recursion involving only tail recursion can always be converted to direct recursion. The authors also show that the termination rule of not expanding directly recursive procedures is not by itself strong enough to avoid infinite expansion.

The assumptions used in the paper are modest, the data structures used are common to compilers, and the analysis techniques are not expensive. The paper itself is short and clear.