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! 🎉
Top comments (0)