```Subject: Re: Midfunction Recursion
From: Erik Naggum <erik@naggum.no>
Date: 23 Oct 2002 15:31:57 +0000
Newsgroups: comp.lang.lisp
Message-ID: <3244375917435651@naggum.no>

* Travis Whitton
| While I don't have any problem understanding recursive functions where
| the function call is the last statement in the function, this particular
| function calls itself in the middle, and I can't rationalize exactly how
| it works.

Pardon me, but this made me laugh out loud.  All that work by the Scheme
freaks to teach people recursion and to abuse it for iteration, and the
end result is that someone does not get it except for iteration!  It had
to happen.  Nothing personal, Travis, this is your teachers' fault.

| Can someone explain how calling uncompress inside of uncompress' let
| statement works?

Exactly like calling from somewhere else.  But watch the arguments.  The
recursive call causes the tail to be processed before the head.  This
means that when you call (uncompress '((3 1) (2 0))), the first thing it
does is compute (uncompress '((2 0))), which yields (0 0) by prepending a
list of two 0's to the empty list.  Then the rest of the first call takes
control and prepends a list of three 1's to the tail it computed first,
(0 0), and you get (1 1 1 0 0).