How do I go past the Recursion Limit?

Question

I have a simple program that defines the Ackermann function in JavaScript:

function ack(m,n,p){
    if(p==0) return m+n;
    if(n==0&&p==1) return 0;
    if(n==0&&p==2) return 1;
    if(n==0&&p>2) return m;
    return ack(m,ack(m,n-1,p),p-1)
}

as defined by here, for the purposes of evaluating tetration and higher extensions. This works for the adding of integers, as:

ack(m,n,0);

Multiplication:

ack(m,n,1);

Expontiation:

ack(m,n,2);

And, Tetration:

ack(m,n,3);

This attempt fails at values m, n > 2, throwing: InternalError: too much recursion. I know this typically occurs with non-terminating recursive functions (like var inf_rec = x => inf_rec(x)), but this function does terminate.

Question

Is there any way to bypass the InternalError?

Edit

What should I do instead, since I obviously need a deeper cell stack?

Link to relevant non-recursive code (you'll need to translate it to _JavaScript_) http://stackoverflow.com/a/10744545/1615483 — Paul S., Jan 07 '15 at 01:26
@PaulS. I rewrote the OP's code in a [**non-recursive way**](http://jsfiddle.net/Ld3cmu1s/) and while it never reaches the maximum stack size, it also never finishes for `ack(3, 3, 3)`. How long those computations should take? — plalx, Jan 07 '15 at 02:11
@plalx: The Ackermann function can produce *extremely* large results even for small input values. — Greg Hewgill, Jan 07 '15 at 02:14
@GregHewgill Yes, it seems so, but could it really take more than 5 minutes or that looks suspicious? — plalx, Jan 07 '15 at 02:35
The whole point with Ackerman is to demonstrate complex recursion. See http://youtu.be/i7sm9dzFtEI — Sylwester, Jan 07 '15 at 06:25

score 2 · Answer 1 · edited May 23 '17 at 12:20

2

No this depends on the maximum stack size set for each browser. There is a link here that contains an answer with all of the related stack maximum sizes for each browser with a method for viewing the stack in that specific browser.

edited May 23 '17 at 12:20

Community

1
1

answered Jan 07 '15 at 00:44

Camron_Godbout

1,583
1
15
22

Is there a way to bypass this? – Conor O'Brien Jan 07 '15 at 00:52
I would assume only by recompiling each browser. These values the result of some deep technical choices in the JavaScript engines – Jason Sperske Jan 07 '15 at 00:56
@ConorO'Brien For this case you may want to store the computed values so that they don't get recomputed and making the stack huge. – Derek 朕會功夫 Jan 07 '15 at 00:59
@Derek朕會功夫 How might I go about doing this? – Conor O'Brien Jan 07 '15 at 01:00

plalx · Answer 2 · 2015-01-07T02:43:24.497

I rewrote your own implementation in a non-recursive way and it finishes for ack(2, 3, 3); now, which is 65536, but it seems to never reach the end of computation for something like ack(3, 3, 3);. I did not get any stack overflow errors however, even after waiting at least 5 minutes for the computation to end... that looks suspicious.

Here's the implementation:

var logEl = document.getElementById('log');


log('ack(1, 2, 0)', ack(1, 2, 0));
log('ack(8, 2, 1)', ack(8, 2, 1));
log('ack(4, 2, 2)', ack(4, 2, 2));
log('ack(2, 3, 3)', ack(2, 3, 3));

//ack(3, 3, 3) never seem to end, but I did not get a stack overflow error...

function ack(m, n, p) {
    var callStack = [[m, n, p]],
        valueStack = [],
        item;
    
    while (item = callStack.pop()) {
        m = item[0];
        n = item[1] !== null? item[1] : valueStack.pop();
        p = item[2];
        
        if (p === 0) { valueStack.push(m+n); continue; }
        if (n === 0 && p === 1) { valueStack.push(0); continue; }
        if (n === 0 && p === 2) { valueStack.push(1); continue; }
        if (n === 0 && p > 2) { valueStack.push(m); continue; }
        
        callStack.push([m, null, p - 1]);
        callStack.push([m, n - 1, p]);
        
    }
    
    return valueStack.pop();
}

function log(exp, val) {
    var li = document.createElement('li');
  
    li.textContent = exp + ' -> ' + val + '\n';
    logEl.appendChild(li);
}

<ul id="log"></ul>

Why does the code snippet evaluate in seconds, if it takes so long? — Conor O'Brien, Jan 07 '15 at 02:45
@ConorO'Brien The listed computations takes milliseconds, even for `ack(2, 3, 3)` which was producing a stack overflow error with your code, but it does take forever with `ack(3, 3, 3)`. I have no idea wheter this is normal or not. — plalx, Jan 07 '15 at 02:47

score 0 · Answer 3 · answered Jan 07 '15 at 00:53

The error does not have to do with non-terminating vs terminating call stacks. Instead it has to do with how deep the call stack is. There is a limit to how many function calls you can recursively make, depending on the browser implementation. The only way to bypass this issue is to assure that your call stack never hits that limit.

How do I go past the Recursion Limit?

Question

Edit

3 Answers3