Re: Have you tried recursion with Ackerman?

"Heinrich Wolf" <invalid@xxxxxxxxxxxxxxx> wrote in message
news:ejstqc$qhp$1@xxxxxxxxxxxxxxxxxxxxx

Ackerman(0, y) := y + 1;
Ackerman(x, 0) := Ackerman(x - 1, 1);
Ackerman(x, y) := Ackerman(x - 1, Ackerman(x, y - 1));
[...]
On friday you wrote, the hailstone recursion can be substituted by
a loop. I'm afraid, the Ackermann recursion cannot be substituted
totally by loops. From playing and trying I found some partial
solutions by loops. But I cannot proof those.

The hailstone function is tail-recursive. That is a special case,
very easily linearised. In general, the call at the end of a tail-
recursive function can be transformed to a jump without changing
the function's semantics. That jump makes the entire function a
repeat-until loop.

The Ackerman call graph is a tree. While it's possible to construct
a loop that emulates two nested loops, I don't know if that scales
up to an arbitrary number of loops. Obviously, it scales up to any
_known_ number. But I don't know if it's still possible if the number
is not known in advance.

Groetjes,
Maarten Witlink


.

Relevant Pages

  • Re: Loop non-jump
    ... think the loop is a tough jump, at least I found it so for a long time, ... On land I can get ... loops), but you could also try just jumping up and down again without ... Maybe trying to add a simple vertical hop without rotation is indeed ...
    (rec.sport.skating.ice.recreational)
  • Re: Looking for a way to convert dec to bin
    ... things like Exit Do or Exit For. ... They're effectively a form of GoTo, ... What makes goto so bad is that you can use it to jump *into* ... loops and hence violate the flow of the code (not sure of the technical term ...
    (microsoft.public.vb.general.discussion)
  • RETURN statement (NEWBIE question)
    ... I have two nested do loops in a function. ... If I put a RETURN statement in the inner loop, will my program then jump ... to the outer loop or will it jump out of both loops? ...
    (comp.lang.fortran)
  • Re: RETURN statement (NEWBIE question)
    ... > I have two nested do loops in a function. ... > If I put a RETURN statement in the inner loop, ... > to the outer loop or will it jump out of both loops? ... > Aalborg University, Aalborg, Denmark. ...
    (comp.lang.fortran)