Thread View: comp.sys.transputer
2 messages
2 total messages
Started by "Phillip M. Hallam-Baker"
Tue, 09 Oct 1990 00:56
Re recursion and the towers of Hanoi.
Author: "Phillip M. Hallam-Baker"
Date: Tue, 09 Oct 1990 00:56
Date: Tue, 09 Oct 1990 00:56
28 lines
1948 bytes
1948 bytes
Dear Net, Isn't all this biz about recursion straying a little from the point? Any recurisve routine can be written without explicit recursion, all that is required is some method of saving the extra state which would be stored on the stack. Some recursive routines have an upper bound on the total amount of state they require such as the towers of hanoi problem. These are the so called "non recursive solutions". However I note that the Hanoi algorithm presented includes "do repeatedly" isn't this starting to look just a teensy weensy bit like a recursive definition trying to get out. The whole point about recursion is not that you can do without it. You can write any program in FORTRAN if you realy have to. Recursion allows in many cases a much more elegant description of the algorithm, a much more abstract description (this is abstraction in the computing sense ie stripped of unnecessary and confusing junk - ie abstraction is a virtue). To present any language as definitive if it lacks recursion 30 odd (or there abouts) years after the discovery of quicksort is rather ridiculous. Ok it may be a bit tricky to allow dynamic allocation in a parallel language - but VMS was doing this almost 20 years ago (yes you can solve the towers of Hanoi in VMS DCL!) Even the FORTRAN 9X (eventualy to become 10X) proposal has accepted the need for recursion, surely occam should as well? Phill M Hallam-Baker Oxford University Nuclear Physics Lab
Re: Re recursion and the towers of Hanoi.
Author: Rob Kurver
Date: Mon, 08 Oct 1990 11:49
Date: Mon, 08 Oct 1990 11:49
37 lines
2249 bytes
2249 bytes
In some message, Phill M Hallam-Baker writes:
> The whole point about recursion is not that you can do without it.
> You can write any program in FORTRAN if you realy have to. Recursion allows
> in many cases a much more elegant description of the algorithm, a much more
> abstract description (this is abstraction in the computing sense ie stripped
> of unnecessary and confusing junk - ie abstraction is a virtue).
Amen.
> To present
> any language as definitive if it lacks recursion 30 odd (or there abouts)
> years after the discovery of quicksort is rather ridiculous. Ok it may be
> a bit tricky to allow dynamic allocation in a parallel language - but VMS
> was doing this almost 20 years ago (yes you can solve the towers of Hanoi
> in VMS DCL!) Even the FORTRAN 9X (eventualy to become 10X) proposal has
> accepted the need for recursion, surely occam should as well?
I seem to recall that the original Occam definition has recursion - the
Inmos transputer implemantation is deficient in this respect. The reason
for not allowing recursion (as well as some other things) is to keep the
program completely static. This helps when you need to allocate
workspaces for multiple processes etc: it's easier for the compiler
writer to implement, and it's even possible to apply heuristics to get a
particularly good memory layout. (Ever wondered why Occam uses the
internal memory better than the average 'alien language'?)
BTW: IMHO, recursion isn't the only thing missing from Occam... But then,
I guess I'm a real C weeny.... :-)
Cheers. - Rob
--
PACT Rob Kurver
Foulkeslaan 87 rob@pact.nl
2625 RB Delft
The Netherlands +31 15 616864
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads