ackermann function

This is a discussion on ackermann function within the C++ Programming forums, part of the General Programming Boards category; Is my implementation correct? I'm assuming it's not because I keep getting zero returned... Where am I going wrong? Code: ...

  1. #1
    village skeptic
    Join Date
    Aug 2008
    Posts
    31

    ackermann function

    Is my implementation correct? I'm assuming it's not because I keep getting zero returned... Where am I going wrong?
    Code:
    //implementation of the recursive ackermann function
    int ack(int m, int n)
    {
        if (m == 0){
            return n+1;
        }
        else if(m > 0){
            ack(m-1, 1);
        }
        else if((m > 0) && (n > 0)){
            ack(m-1, ack(m, n-1));
        }
    }//end ack

  2. #2
    Registered User Kernel Sanders's Avatar
    Join Date
    Aug 2008
    Posts
    61
    The third condition is never used. If m>0 the second will be evaluated whether n>0 or not. You also need to return ack(whatever) instead of just invoking it. As is the value is never used or returned, just computed and thrown out

  3. #3
    village skeptic
    Join Date
    Aug 2008
    Posts
    31
    Quote Originally Posted by Kernel Sanders View Post
    The third condition is never used. If m>0 the second will be evaluated whether n>0 or not. You also need to return ack(whatever) instead of just invoking it. As is the value is never used or returned, just computed and thrown out
    My mistake on the missing return bit. I'm not sure why I overlooked that... Anyway, I've updated the conditions of the second else if - they should now properly match the wikipedia entry.

    Code:
    //implementation of the recursive ackerman function
    int ack(int m, int n)
    {
        if (m == 0){
            return n+1;
        }
        else if((m > 0) && (n == 0)){
            return ack(m-1, 1);
        }
        else if((m > 0) && (n > 0)){
            return ack(m-1, ack(m, n-1));
        }
    }//end ack

  4. #4
    village skeptic
    Join Date
    Aug 2008
    Posts
    31
    A quick question about the above, however. The book I'm working through suggested I implement the function to learn about recursion. The book also stated that this is a popular demonstration of recursion that is commonly used in CS courses all over the place.

    anyway, my question is: What exactly is the point of the function? What purpose does it serve? The wikipedia page turned out to be a little too 'mathematically verbose'.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,892
    The ackermann function has no practical purpose.

    It's importance lies in mathematical theory. There are several formalisms that are important to decide on the computability of a function. Nowadays the most important of those are the Turing machine and lambda calculus. It is said that if a function can be expressed as a Turing machine or in lambda calculus, it is computable.
    Before those were developed, however, there was a different formalism. This formalism defined the set of what is now known as "primitive recursive functions". At the time, it was theorized that this formalism was sufficient for describing all computable functions.
    The ackermann function is a counterexample for this. While it is computable, it cannot be expressed using the old formalism. Thus its importance in theoretical mathematics: it forced people to come up with new formalisms. (They found µ-recursion, Turing machines and lambda calculus, all of which were later proven to be equivalent in expressiveness.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  3. Troubleshooting Input Function
    By SiliconHobo in forum C Programming
    Replies: 14
    Last Post: 12-05-2007, 06:18 AM
  4. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  5. const at the end of a sub routine?
    By Kleid-0 in forum C++ Programming
    Replies: 14
    Last Post: 10-23-2005, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21