To Be Creative: recusion

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:

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:

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).

02 July 2015

Tail Recursion

Tail recursion is special case of recursion where the function calls itself as the last statement in the method.

From wikipedia:

Tail calls can be implemented without adding a new stack frame to the call stack.

Here's an example of Sum of Ints function that sum Integers between a and b

so when call sumOfInts(1, 4) would equals 1 + 2 + 3 + 4 = 10

First implementation using non-Tail recursion:

def sumOfInt(a: Int, b: Int): Int =

if (a > b) 0 else a + sumOfInt(a + 1, b) // last stmt is a call to the same function and then add some value to it (non tail recursion)

The second implementation using a Tail recursion function:

def sumOfInt2(a: Int, b: Int): Int =

        sumOfAllInts(a, b, 0)                    

def sumOfAllInts(a: Int, b: Int, t: Int): Int =

if (a > b) t else sumOfAllInts(a + 1, b, t + a) // last stem is a call to the same function only (tail recursion)

Test

sumOfInt(1, 100000000)                        //> java.lang.StackOverflowError

sumOfInt2(1, 100000000)                       //> res2: Int = 987459712

Conclusion

The Tail recursion version using the same stack frame on each call (vs the non-tail recursion which will use a new stack frame for each call for the reclusive method)

See this question and read the answer to understand about Tail Recursion: http://cs.stackexchange.com/questions/6230/what-is-tail-recursion