Skip to content

Instantly share code, notes, and snippets.

@sackeyjason
Last active July 8, 2019 04:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sackeyjason/b299c6e9251d534256b3964ea85e309f to your computer and use it in GitHub Desktop.
Save sackeyjason/b299c6e9251d534256b3964ea85e309f to your computer and use it in GitHub Desktop.
Ackermann–Péter function, with and without recursion. Faster without!
// "Canonical", recursive
const ap = (m, n) => {
if (m === 0) return n + 1;
if (m > 0 && n === 0) return ap(m - 1, 1);
if (m > 0 && n > 0) return ap(m - 1, ap(m, n - 1));
};
// Non-recursive. Faster, and won't exceed call stack size!
// But maybe the array will get too huge.
const ap2 = (m, n) => {
let cm = [];
while (true) {
if (m === 0) {
if (!cm.length) return n + 1;
m = cm.pop();
++n;
} else if (m > 0 && n === 0) {
--m;
n = 1;
} else if (m > 0 && n > 0) {
--n;
cm.push(m - 1);
}
}
};
// minified, golfed
a=(m,n)=>m?n?a(m-1,a(m,--n)):a(--m,1):++n
// It can go smaller:
// https://codegolf.stackexchange.com/questions/40141/the-ackermann-function
// non-recursive minified (WIP)
ax=(m,n)=>{
for(cm=[];m+cm.length;){
m?n?(cm.push(m-1),--n):n=(--m,1):m=cm.pop(++n)
}
return ++n
}
module.exports.ap = ap;
module.exports.ap2 = ap2;
module.exports.ap3 = ap3;
module.exports.a = a;
module.exports.ax = ax;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment