Skip to content

Instantly share code, notes, and snippets.

@lovasoa
Last active March 27, 2016 13:59
Show Gist options
  • Save lovasoa/8407923f8d9740582e32 to your computer and use it in GitHub Desktop.
Save lovasoa/8407923f8d9740582e32 to your computer and use it in GitHub Desktop.
Non-recursive definition of ackermann function
// Non-recursive definition
function ack(m,n) {
var ans, mn, pile;
for (pile=[[m,n]]; mn = pile.pop();) {
var m = mn[0], n = mn[1];
if (n === -1) n = ans;
if (m === 0) ans = n + 1;
else if (n === 0) pile.push([m-1, 1]);
else {
pile.push([m-1, -1], [m, n-1]);
}
}
return ans;
}
// Recursive definition
function ackr (m, n) {
if (m===0) return n+1;
else if (n===0) return ackr(m-1, 1);
return ackr(m-1, ackr(m, n-1));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment