[metapost] Re: all intersections between two paths

[Laurence Finston]

On Mon, 17 Jan 2005, Hans Hagen wrote:

> Laurence Finston wrote:
>
> > I _always_ try to eliminate recursion in my programs wherever possible,

> there's nothing wrong with recursion; in tex/mp, try to use
> tail recursion and
> then there are no limits

I don't think there's anything _wrong_ with it.  As I understand it,
where tail recursion is possible, there is indeed no problem.
Roughly speaking, and again as I understand it,
in C and C++, the price of a function call
is a stack frame, whereas the price of a loop is a handful of machine
instructions.
The price of an additional, recursive call to a function is another stack
frame, whereas the price of an additional iteration is testing a
conditional and a jump, i.e., negligible.
I don't know whether optimizing compilers (or perhaps the run-time system?)
can recognize where tail recursion is possible and eliminate
stack frame nesting;  nor do I know how a programmer could tell the
compiler to do this, where possible, nor whether it would be wise for a
programmer to depend on this behavior.  If you or anyone else knows
about this subject, I'd be very interested in learning more.

In GNU 3DLDF, the price of a
macro call that of a loop is not too different, since macros and
loops are implemented in a similar way.  However, each additional call to
a macro has the same price as the first one, whereas the price of an
additional iteration is negligible.  Since macro expansion and looping are
similar in MF and GNU 3DLDF, I'm fairly sure the situation is similar in
MF, notwithstanding the differences in implementation, unless, of
course, MF can use tail recursion.  I don't know how it does this, or
whether one can depend on it always being done.  I believe that
in C, tail recursion is possible when the enclosing function exits
immediately after the recursive function call, or at least
when no local variables are accessed and the values of no static or
global variables are changed after the recursive function call.
Again, if anyone can "lift the veil of ignorance", this would be much
appreciated.

Laurence