 | | RE: Would-be hacker queries. —Joel Shafer
|
| | | Searching and replacing is a good example of recursion. Suppose that you are editing a document and want to replace every occurrence of the word "the" with the word "then". Here is one way that the program could handle it. Function (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | |
| | | | | RE: Would-be hacker queries. —Ralph Hempel
|
| | | | | (...) You are right, but recursion carries a terrible price in terms of stack usage. Most recursion is useful for implementing search and traversal algorithms, but unless the hardware supports DEEP stacks for the worst case, the problem is almost (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | |
| | | | | | | recursion (was RE: Would-be hacker queries.) —Joel Shafer
|
| | | | | | | Here is an interesting article on implementing stack free recursion. (...) -- Did you check the web site first?: (URL) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | | | |
| | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Paul Speed
|
| | | | | | | | Hi, Important clarification: "data stack" free recursion. This is an important significance. It's really only useful for systems with no data stack.... or alternately as an interesting conversation piece. What's usually more clever is using data (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | | | | |
| | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —John A. Tamplin
|
| | | | | | | | | (...) Actually, he goes on to show that in some cases you can eliminate call stack recursion using simple transforms as well. (...) For example, JVM does this by keeping a frame stack of methods that have been executed. The interpreter main loop (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | | | | | |
| | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Anders Isaksson
|
| | | | | | | | | | John A. Tamplin skrev i meddelandet ... (...) Are you sure? I have faint memories from University of a function called 'The Ackermann Function' which was 'recursive in all directions', and couldn't be expressed iteratively. Of course, my memory is (...) (26 years ago, 12-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —John A. Tamplin
|
| | | | | | | | | | (...) I am not familiar with that function, but I believe I recall a proof in a graduate CS theory class that any recursive algorithm could be transformed into an iterative one. Do you have a reference for this function? For practical purposes, (...) (26 years ago, 12-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Ben Laurie
|
| | | | | | | | | | | (...) I seem to remember the point of the Ackermann function is that the amount of computation required to evaluate it explodes very rapidly with small changes in parameter values, and it is recursive and rather simple. I also seem to remember "so (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | | |
| | | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Malcolm S. Powell
|
| | | | | | | | | | | | | Ackermann's Function ---...--- Function ack(n, m: integer): integer; Begin If m = 0 Then ack = n + 1 Else If n = 0 Then ack = ack(m-1, 1) Else ack = ack(m-1, ack(m, n-1)) End; Funny what sticks in your mind! As far as I know, the only significance (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | | | | |
| | | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Peter Hesketh
|
| | | | | | | | | | | | In article <373AA2D3.2A4E812B@a...up.co.uk>, Ben Laurie <ben@algroup.co.uk> writes (...) Is this the same Mr Ackerman who invented Ackerman steering? (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Ben Laurie
|
| | | | | | | | | | (...) And, BTW, isn't this intuitively obvious, since CPUs are, in fact, iterative? Cheers, Ben. -- (URL) grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Rich Clemens
|
| | | | | | | | | | (...) How so? -- Richard Clemens Associate Professor Computer Science Department West Virginia Wesleyan College Buckhannon, West Virginia 26201 clemens@wvwc.edu 304.473.8421 ----- Original Message ----- From: Ben Laurie <ben@algroup.co.uk> To: John (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Ben Laurie
|
| | | | | | | | | | (...) What do you mean? The algorithm a CPU uses (at least, any I'm familiar with) to execute code is an iterative algorithm (i.e. fetch instructions, decode, execute, go round again). Cheers, Ben. -- (URL) grandfather once told me that there are (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Rich Clemens
|
| | | | | | | | | | Is that a function of the CPU or the OS? -- Richard Clemens Associate Professor Computer Science Department West Virginia Wesleyan College Buckhannon, West Virginia 26201 clemens@wvwc.edu 304.473.8421 ----- Original Message ----- From: Ben Laurie (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Ben Laurie
|
| | | | | | | | | | (...) Is this a windup? The CPU, of course! (...) ^^^...^^^ of what? (...) Cheers, Ben. -- (URL) grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the first group; (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —Rich Clemens
|
| | | | | | | | | | If the CPU then the hardware (datapath) or the microcode? -- Richard Clemens Associate Professor Computer Science Department West Virginia Wesleyan College Buckhannon, West Virginia 26201 clemens@wvwc.edu 304.473.8421 ----- Original Message ----- (...) (26 years ago, 13-May-99, to lugnet.robotics)
|
| | | | | | | | | | |
| | | | | | | | | | Re: recursion (was RE: Would-be hacker queries.) —JR Conlin
|
| | | | | | | | (...) Let me say that I have not looked at the algorythm in question, yet, so forgive me if this is their solution... (...) The SmalltalkVM my last company built used much the same idea, however, one might say that it was a truely recursive (...) (26 years ago, 12-May-99, to lugnet.robotics)
|
| | | | | | | | |
| | | | | | | RE: Would-be hacker queries. —Todd Lehman
|
| | | | | | (...) Don't modern implementations of Lisp/Scheme/Logo automatically convert tail- recursion into iteration? --Todd (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | | |
| | | | | | | | RE: Would-be hacker queries. —John A. Tamplin
|
| | | | | | (...) Yes, as do decent implementations of traditional compiled languages. For example, GCC converts the following: int f(int v) { if(v<2) return v; return f(v-1); } into int f(int v) { while(v>1) { v--; } return v; } Not terribly useful, but (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | | | |
| | | | | RE: Would-be hacker queries. —Joel Shafer
|
| | | | It's too bad that recursion pays the price of stack usage. Recursion is almost always a more elegant solution and is more easily maintained. But as it is, recursion should only be used when you know that the worst case scenario won't overflow the (...) (26 years ago, 11-May-99, to lugnet.robotics)
|
| | | | |
