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).  

  The smart thing about this solution is that it avoids copying the list it
  has already constructed.  That is indeed a good algorithm, but if one is
  concerned about wasted resources, reversing the list first does exactly
  the same good without the cost of the recursion.

-- 
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.