 | | RE: Would-be hacker queries.
|
|
(...) problem. (...) You know, I have never really liked the factorial example of recursion. Honestly, how many times have you really needed to generate a factorial in general experience? I feel a better example is building stuff with LEGO. In this (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | RE: Would-be hacker queries.
|
|
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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | RE: Would-be hacker queries.
|
|
(...) 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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | RE: Would-be hacker queries.
|
|
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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | recursion (was RE: Would-be hacker queries.)
|
|
Here is an interesting article on implementing stack free recursion. (...) -- Did you check the web site first?: (URL) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | RE: Would-be hacker queries.
|
|
(...) 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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | RE: Would-be hacker queries.
|
|
(...) Don't modern implementations of Lisp/Scheme/Logo automatically convert tail- recursion into iteration? --Todd (25 years ago, 11-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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 (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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, (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
(...) 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; (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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 (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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 ----- (...) (25 years ago, 13-May-99, to lugnet.robotics)
|
| |
| | Re: recursion (was RE: Would-be hacker queries.)
|
|
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? (25 years ago, 13-May-99, to lugnet.robotics)
|
