Subject: Re: Newbie: How does a lambda recurse? From: Erik Naggum <erik@naggum.net> Date: Mon, 20 May 2002 05:25:24 GMT Newsgroups: comp.lang.lisp Message-ID: <3230861121663553@naggum.net> * "P.C." <per.corell@privat.dk> | 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.