How to calculate the number of recursive calls made to the Ackerman() function in C

Question

I tried writing this code to calculate the Ackerman value and also the number of times the function is called. However, the counter is stuck at 0 all the time. Could you help me out?

/*
A(m,n) =    n+1, if m==0
A(m,n) =    A(m-1,1), if m>0 and n==0
A(m,n) =    A(m-1,A(m,n-1)), if m>0 and n>0
*/
#include<stdio.h>
static int w=0;
int ackerman(int m,int n)
{

    w=w+1;
    if(m==0)
        return n+1;
    else if(m>0 && n==0)
        return ackerman(m-1,1);
    else if(m>0 && n>0)
        return ackerman(m-1,ackerman(m,n-1));
}
int mainackerman()
{
    int m,n;
    scanf("%d %d",&m,&n);
    printf("%d %d",ackerman(m,n),w);
    return 0;
}

score 5 · Answer 1 · edited May 23 '17 at 11:52

You have a sequence-point issue. On the same line as you are calling ackerman, you are using a value that is affected by that call. This is undefined behaviour. Do this instead:

int result = ackerman(m,n);
printf("%d %d", result, w);

There is a good question on StackOverflow with some excellent answers related to sequence-points. It's related to C++, but the idea is essentially the same as for C.

How to calculate the number of recursive calls made to the Ackerman() function in C

1 Answers1