Recursive Calls in JavaScript

Programming languages often limit the number of nested calls a recursive function is allowed to make.

Consider this simple example in JavaScript. An adder function recursively calls an inner function loop exactly n times and returns n as the result:

function adder(n) {
  function loop (i) {
    if (i == n) {
      return n;
    }
    return loop(i + 1);
  }

  return loop(0);
}

console.log(adder(10));
console.log(adder(1000));
console.log(adder(100000));

This code works fine for small values of n. But with larger values eventually we run out of stack space and crash 💥

pi@raspberrypi:~/Documents $ node adder.js
10
1000

/home/pi/Documents/adder.js:2
  function loop (i) {
                ^
RangeError: Maximum call stack size exceeded

The problem is that loop keeps getting added to the call stack for subsequent i values:

adder(10)
loop(0)
loop(1)
loop(2)
loop(3)
...

Once we reach the end of the stack we are done. And there is only 492 Kb of stack space on our test system:

pi@raspberrypi:~/Documents $ node --v8-options | grep -B0 -A1 stack_size
  --stack_size (default size of stack region v8 is allowed to use (in kBytes))
        type: int  default: 492

Tail Call Optimization

This is where we leave off with JavaScript (for now).

But there is more to the story. Some other languages and tooling support a concept called tail call optimization (TCO) that prevents the call stack from growing indefinitely.

In a language with TCO the call stack grows no larger than:

adder(10)
loop(...)

Subsequent calls to loop are not added to the stack. Or at least conceptually we can view it this way - the actual implementation details can vary from language to language. But the point is that the stack no longer grows indefinitely, so we can make unlimited use of recursive functions.

Recursive Calls in Scheme

For example, adder works just fine when implemented in Scheme, which requires TCO as part of its language specification:

(import (scheme base) 
        (scheme write))

(define (adder n) 
  (define (loop i)
    (if (= i n)
        n
        (loop (+ i 1))))
  (loop 0))

(write (adder 10)) (newline)
(write (adder 1000)) (newline)
(write (adder 100000)) (newline)
(write (adder 10000000)) (newline)

pi@raspberrypi:~/Documents $ cyclone adder.scm
pi@raspberrypi:~/Documents $ ./adder
10
1000
100000
10000000

The code runs fine even for a massive value such as 10,000,000.

Conclusion

So, does tail call optimization make Scheme "better" than JavaScript? Not at all! Each language just emphasizes a different coding style. Functional languages such as Scheme, Haskell, and Erlang typically use recursion for looping. Without TCO they would be useless.

In contrast imperative languages such as JavaScript, Go, and C use iteration for looping with for, foreach, while, and friends. Since this is the widely accepted style there just isn't a need to optimize for recursion in these languages.

Alright, that's all for now.
Cheers! 🎉