0
$\begingroup$

how does that recursion work 

#include <stdio.h>


int ack(m,n)
int m,n;
{
int ans;
if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);
else ans = ack(m-1, ack(m,n-1));
return (ans);
}

int main (argc, argv)
int argc; char ** argv;

{ int i,j;
for (i=0; i<6; i++)
for (j=0;j<6; j++)

printf ("ackerman (%d,%d) is: %d\n",i,j, ack(i,j));
}
Improve this question
$\endgroup$
1
  • $\begingroup$ There's no need to include the code: Ackermann's function has a simple mathematical definition. As for the run time on an "average PC", you need to look at roughly how many instructions are executed when the program runs, and you may as well assume one instruction per clock cycle. $\endgroup$
    – David Richerby
    Oct 26, 2014 at 20:12

1 Answer 1

Reset to default
1
$\begingroup$

The Ackermann–Péter function works as advertised, while not being primitive recursive. There is an abundance of literature on this function and its execution time. Growth in the second parameter depends on the first, it is a bit like going from counting to addition to multiplication to exponentiation ...
The execution time of the code shown is entirely irrelevant, as the values will almost immediately overflow anyways - googol is small compared to ack(4,2), googolplex dwarfed by ack(5, 1).

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.