Re: general algorithm + ackermann question

On Jan 29, 9:26 pm, jason.s.tur...@xxxxxxxxx wrote:
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.

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."

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

        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;
            }

        }


If I interpret your (somewhat mangled ;-) terminology correctly, what
the assignment is asking you to do for a "dynamic solution" is fill in
a 2d table indexed on m and n and sized according to the "topmost"
values of m and n in the recursion. Fill in m=0,1,2 and n=0, which is
easy. Then do the rest of the table in an order such that you only
look at entries already filled in. After you have worked that out,
you'll see that you only need to keep a couple of rows of the table
around because the recursion never looks back by more than one row.
Other economies are likely to exist. I'll let you work them out.
.

Relevant Pages

  • 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, ... int ackDyn ... switch ...
    (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: 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)
  • Re: Grammatical Recursion
    ... On 2004-12-17, Des Small wrote: ... The Ackermann function, for example: ... > def Ack: ... which might as well be recursion. ...
    (sci.lang)