[metafont] Re: [metapost] recursion in MP/ MF [was: all intersections betwee

[Laurence Finston]

I'm taking the liberty of posting this to the mailing lists
(might as well use them while they're still around), because you're
probably not the only person who doesn't know this.

I'm also not the person on this list who knows the most
about this subject, so corrections are welcome.

On Wed, 19 Jan 2005 MASCHLER at vms.HUJI.AC.IL wrote:

> Sorry for this naive question.

I don't think that's something anyone has to apologize for.

>
> Can you explain to me in plain language what is the difference between
> recursion and tail-recursion?

This example uses C, but I believe the situation is identical with other
compiled languages, such as Fortran and Pascal.

When a function invokes itself, that's called recursion.  For example,

int
a(int b)
{
   if (b > 0)
      return a(b - 1);
   else
      return -1;
}

The call `a(b- 1)' is a recursive call to `a()'.  A popular example for
teaching recursion in textbooks is the factorial function.

When a function is called, the run-time system creates something called a
"stack frame" which includes the arguments passed to the
function and information such as the address where execution should resume
after the function returns.  A stack frame is really just data that's
pushed onto the stack of the process or the thread.  One can examine these
stack frames by using a debugger, such as GDB.

If you call a function recursively, it creates a new stack frame, so if a
function recurses a lot, this can cause many stack frames to be created.

For example, calling this version of `a()' will eventually cause your
process to run out of space on the stack:

void
a(int b)
{
   a(b);
}

If a function doesn't "do anything" after the call to itself, it
is possible for the compiler (and/or run-time system?) to remove
the stack frame representing that call, so that the stack frames
don't pile up.  This is called "tail recursion".  Knuth mentions
this somewhere in the _TeXbook_.  That's how I found out about it.

Laurence