Subject:
|
Re: recursion (was RE: Would-be hacker queries.)
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 13 May 1999 10:00:51 GMT
|
Original-From:
|
Ben Laurie <ben@algroup.&AvoidSpam&co.uk>
|
Viewed:
|
1023 times
|
| |
|
|
John A. Tamplin wrote:
>
> On Wed, 12 May 1999, Anders Isaksson wrote:
>
> > 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.
>
> 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?
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 what?" being my reaction when I came across
it :-).
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html
"My 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; there was less competition there."
- Indira Gandhi
--
Did you check the web site first?: http://www.crynwr.com/lego-robotics
|
|
Message has 2 Replies:
 | | 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)
|
Message is in Reply To:
| | 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)
|
21 Messages in This Thread:
  
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
