24 July 2016

Tail Recursion in Nodejs

I've talked about tail recursion in a previous post, today I'll show an example on nodejs.

We have a function that sums numbers starting from 0 to an n number.

We have both version of it, the tail recursion and non-tail recursion version:
1
2
3
4
5
6
7
8
function sumNonTailVersion(n) {
    return (n < 1) ? 0 : n + sumNonTailVersion(n - 1);
}

function sumTailVersion(n, acc) {
    acc = acc || 0;
    return (n < 1) ? acc : sumTailVersion(n - 1, acc + n);
}

Use the following code to test the above two functions:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
try {
    console.log('sumNonTailVersion: ', sumNonTailVersion(1000000));
} catch (e) {
    console.error('sumNonTailVersion: ', e.message);
}
try {
    console.log('sumTailVersion: ', sumTailVersion(1000000));
} catch (e) {
    console.error('sumTailVersion: ', e.message);
}

Run the functions using the following flags:
node --use-strict --harmony-tailcalls file.js

And here's the result:
1
2
sumNonTailVersion:  Maximum call stack size exceeded
sumTailVersion:  500000500000

The non-tail recursion version fail with "Maximum call stack size exceeded"

Note, if we run without the flags "--use-strict --harmony-tailcalls" the nodejs will run without tail recursion optimizations, and both will treated the same (will through the same error above).


Post a Comment