```Subject: Re: how does recursion work?
From: Erik Naggum <erik@naggum.net>
Date: 16 Oct 2000 00:18:03 +0000
Newsgroups: comp.lang.lisp
Message-ID: <3180644283298512@naggum.net>

* "Cadwallader" <ccadwal1@tampabay.rr.com>
| now how does interpreter program execute this?

A recursive function call is just a function call.

| wouldnt it have to get caught in an infinite loop to execute it?  to
| define recur-expt you need the definition for recure-expt, to define
| that recure-expt you need the defintion for recure-expt etc.

You're actually asking about the way Lisp code is represented in
memory more than how the interpreter (or even compiled code)
executes the code.  The function call (recur-expt m (- n 1)) is
represented as a list with three elements: the symbol recur-expt,
the symbol m, and the list of three elements: the symbol -, the
symbol n, and the integer 1.  But how did we get to the symbols?

When you type in expression to the Lisp, they function read is
called upon to turn your textual representation into an in-memory
structure that consists mostly of pointers to objects.  One of
Lisp's great and lasting ideas is that of having an external format
for its internal memory structures and having reader and writer
functions that convert between the two.

I'm sure you know how lists are represented in memory, so let's
consider how symbols are read and represented.  First, the reader
collects all the characters that make up the name of the symbol.
Then it looks up the symbol in the package (a named symbol table),
or creates it there if it didn't already exist, and returns a
pointer to the (new) symbol.  This pointer is stuffed in the list.

The symbol itself has pointers to quite a number of things, among
them the variable value and the functional value.  When you define a
function, you set the functional value slot of the symbol structure,
but the neat thing is that the pointer to the symbol remains the
same.  The symbol also prints the same as before: with its name.

Through this indirection at two different times, we avoid the whole
issue of referring directly to the function.  The Lisp reader makes
the list element refer to the symbol and when the interpreter needs
to call the function, it looks up the functional value slot of the
symbol and calls that value.

It's all exceptionally elegant and simple, and doesn't need any of
the abstract syntax tree nonsense needed in other languages that
haven't figured out that it's pretty damn smart to represent your
code as a data structure from the get-go (I hope you ignored that
elaborate explanation because it made no sense in a Lisp context).

#:Erik
--
I agree with everything you say, but I would
attack to death your right to say it.
-- Tom Stoppard

```