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

Post a Comment