Re: general algorithm + ackermann question

On Jan 29, 9:55 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
jason.s.tur...@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.

Thanks for the reply. Dynamic programming is a method of solving
problems exhibiting the properties of overlapping subproblems and
optimal substructure (described below) that takes much less time than
naive methods. (Wiki def) My interpretation of the def, along with
the comparison of the recursive and dynamic Fibonacci algorithms is
that, the dynamic approach is more iterative, and it stores the value
of the of the value of the function (at that point) at each iteration
into a variable, then it finally returns the variable. So the value
of the variable that is going to be returned, is based on the values
of the previous iteration.

***I think

I'm taking this course online and my professor seems like a nice guy,
but I think he's very busy and hasn't had the time to reply to my
email. My book appears to be useless so far.

Thanks again.

Jason


.

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: Simple recursive functions in Lisp
    ... (labels ((rev (lst acc) ... becomes a loop variable. ... to the naive car/cdr recursion). ... Another way to express Graham's algorithm is iteration. ...
    (comp.lang.lisp)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: Multivalue tail recursion?
    ... programmers. ... Lisp with the idea of using recursion for everything, ... If you don't need to prove properties of your programs, you can ignore such considerations - then iteration constructs are typically easier to read. ...
    (comp.lang.lisp)
  • Re: Software bugs arent inevitable
    ... >> resource-requirement differences between iteration and recursion can be ... make the difference between an elegant solution that runs like a lame duck ... floats have a finite precision will cause that algorithm to give incorrect ...
    (comp.lang.python)