Re: general algorithm + ackermann question

jason.s.turner@xxxxxxxxx writes:

Hi, I am working on an assignment and I'm a bit confused and stuck.

I am to write an Ackermann function using recursion which was no
problem and dynamic version as well. The dynamic version is giving me
crap.

You'll need to define the term "dynamic" since I am not sure what it
means.

1st off according to this Wikipedia article,
http://en.wikipedia.org/wiki/Recursion#Functional_recursion

"A famous recursive function is the Ackermann function which, unlike
the Fibonacci sequence, cannot be expressed without recursion."

Well you can write it in FORTRAN '66 (that was an assignment when I
was a student) and FORTRAN '66 has no recursion. The article has a
point though -- you need to simulate the recursion if the language
does not have it.

2nd thing, can a function be dynamic, yet also be recursive?
Example:

I think so since what is below looks valid, but what does "dynamic"
mean?


int ackDyn(int m, int n)
{

switch (m)
{
case 0:
return n + 1;
case 1:
return n + 2;
case 2:
return 2 * n + 3;
case 3:
return (int)Math.Pow(2, n + 3) - 3;
default:
if (n == 0)
{
return ackDyn(m - 1, 1);
}
else
{
return ackDyn(m - 1, ackDyn(m, n - 1));
}
}

}

I attempted to rework it with no self-calls, based on some info that I
found on the Ackerman function combined with the code above, which
resulted in:

long dynAck(long m, long n)
{
long result = 2;
long stop = n + 3;
switch (m)
{
case 0:
return n + 1;
case 1:
return n + 2;
case 2:
return 2 * n + 3;
case 3:
return (int)Math.Pow(2, n + 3) - 3;
default:
if (n == 0)
{
stop = 4;
}
for (int i = 1; i < stop; i++)
{
result = (long)Math.Pow(2, result);
}
return result - 3;
}

}

It seems to almost work, but not quite.

The problem is that the "formula" for increasing 'm' gets more and
more complex. What you have in the default case is not quite right
(as you have found out) but it is close to what you need for m == 4
but it is wrong for m > 4.

--
Ben.
.

Relevant Pages

  • Re: break
    ... outside switch or loop". ... of the code is that you want to return immediately from sum. ... return something, because sum returns int, and from the context it looks ... There are no situations where you MUST use recursion, however, there ...
    (comp.lang.java.programmer)
  • Re: Recursion
    ... int A ... Not only are the values of the Ackermann function ... enormous, but the recursion depths are also, consequently, enormous. ... is followed by the tower of tower function, and so on, which are ...
    (comp.programming)
  • general algorithm + ackermann question
    ... I am to write an Ackermann function using recursion which was no ... "A famous recursive function is the Ackermann function which, ... int ackDyn ... switch ...
    (comp.programming)
  • Re: general algorithm + ackermann question
    ... I am to write an Ackermann function using recursion which was no ... "A famous recursive function is the Ackermann function which, ... I attempted to rework it with no self-calls, based on some info that I ... If I interpret your terminology correctly, ...
    (comp.programming)
  • Re: why does this work ?
    ... > infinite recursion. ... and since all recursive algorithms are equivalent to ... a counterexample is the Ackermann function: ... int ackermann ...
    (comp.lang.c)