Thread: Recursive Ackermann's function - need help

  1. #1

    Recursive Ackermann's function - need help

    Hello everyone. I'm new to this board. Just discovered it a short while ago while searching for help on homework. Was wondering if anybody here could help me.

    I need to write a recursive version of the Ackermann function/algorithm, which is:

    Ackermann(m,n) = { n+1 if m=0
    Ackermann(m-1, 1) if n = 0
    otherwise Ackermann(m-1), Ackermann(m, n-1))

    Now a direction coding of this function would be:
    int ackermann(int m, int n){
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n -1));

    But this function is probably somewhere along the lines of O^3 as far as Big O is concerned. Which basically means any number halfway to 10 called by the function would take a lot of time. Forget double digit numbers. I need a more efficient version of function.

    What I have in mind is something that involves Dynamic Programming. Making a table through matrix and then storing already calculated integers in that table and then calling them whenever they come up when the function is checking for a base case. This would GREATLY increase the speed. So I have in mind, a for loop with the table. Anybody who could gimme a hand with this, I would greatly appreciate it. Thank you.

  2. #2
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Use iteration, i.e. loops. Can't help you right now cause I'm kinda busy. But if no one helps you by tomorrow, I'll help you then.

  3. #3
    I need a valid response to this problem before 6:30 AM EST tomorrow.

  4. #4
    Señor Member
    Join Date
    Jan 2002
    Ooooo being a little pushy?

  5. #5
    Nope, just procrastination at its best.

  6. #6
    Join Date
    Aug 2001
    This function is *much* slower than O(n^3) I think it's like O(n^n).

    It looks like you could maybe try to do a 2d
    static array and then assign all the elements to 0. Then if a[m][n] != 0, a[m][n] = the computed value otherwise a[m][n] = the recursive definition.

  7. #7
    Thank you, Nick! For that last algorithm. It really put me back on the right track.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function
    By Fork in forum C Programming
    Replies: 3
    Last Post: 10-26-2006, 11:27 AM
  2. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  3. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM