Subject: Re: Newbie: How does a lambda recurse?
From: Erik Naggum <>
Date: Mon, 20 May 2002 05:25:24 GMT
Newsgroups: comp.lang.lisp
Message-ID: <>

* "P.C." <>
| Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack
| overflow can ocour, within a well known number of data.
| Please understand me right, but as everyone know, there are some old rules we
| just agrea, without even asking if the caurse we say so, is a tiny chance, that
| occoured in compleatly different situasions than the one in count.  Reson I say
| so, is that this "rule" have been there since we all had 8k mem to work with,
| but today, ---- Eh , don't computers carry a bit more mem, than when this rule
| was documentet with Pi making stack overflow.
| _When_ do a recursive function cause this problem, --- and do this still justify
| that saying recursion, we emidiatly say "no-no, you just overflow the stack " ;
| I don't need to overflow any stack, if I know what I do, and if I know that this
| function working on this known set of data ,will _never_ overflow any
| stack. ------ or are we just stubbern old fanatics ,that just react from the
| rules, settled under compleatly different circumstances ,back then in the
| stoneage ?
| Do these old rules still rule, or is this also a matter about ideology ,that if
| anyone accept that you _can_ use recurtion, everyone have to give up their pony,
| and start riding another one.

  Per, please take an English course.  This stuff is just too hard to read.

  After considerable study of your garbled language and thinking, I believe
  you may be satisfied with replies to different questions than you appear
  to ask:

  Is recursion always bad?  No, it is not.

  When is recursion bad and iteration good?  When iteration requires no new
  storage per iteration, or less storage per iteration than recursion.

  When is recursion good and iteration bad?  When (1) you traverse the list
  forwards and backwards and maintain some state for each iteration that
  you unwind or something in the backward pass, and (2) your algorithm
  requires that you be able to backtrack if you make a mistake.

  There is never enough memory for all tasks.  You do in fact run out of
  memory every once in a while even without recursion.  However, most
  systems are set up allow for a bigger heap than stack, and you can run
  out of stack faster than you run out of heap.  Stack is not garbage-
  collected until you return from the allocating frame.  However, there is
  no _fundamental_ difference between using heap or stack space, so what
  you think is a rule against recursion is a rule against recursion where
  iteration is clearly more efficient.

  Since Scheme has a chosen a syntax and a culture using it that reinforce
  recursion at the cost of understanding iteration, many Scheme freaks fail
  to grasp that the iteration that results from their tail recursion has a
  number of internal language requirements.  E.g., the named let, however,
  can easily be implemented in Common Lisp, since it is a local phenonmenon
  and a simple rewriting of the apparently recursive form to iteration is
  fairly trivial.  However, mutually recursive functions are harder to
  rewrite, and that is where the Scheme solution requires language support.
  Failure to understand that this requires language support for making a
  tail call into a tail jump and reusing the caller's call frame causes
  massively wasteful programming styles.

  So, over time, Scheme has come stand for the community of people who do
  not care about memory consumption and think it is somebody else's fault
  when they run out of memory, because they are religious about their
  recursion and are probably not sufficientl skilled to rewrite them to
  iterative form, to boot.

  Ignorance of the real machine is never a good thing for a programmer.
  For that matter, ignorance of the real world is never a good thing.
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.

  70 percent of American adults do not understand the scientific process.