Sunday, 2 July 2017

Kotlin: tailrec - Permanent fix for Painful StackOverflowError



Parameters and local variables are allocated on the stack (with reference types the object lives on the heap and a variable references that object). The stack typically lives at the upper end of your address space and as it is used up it heads towards the bottom of the address space (i.e. towards zero).

Your process also has a heap, which lives at the bottom end of your process. As you allocate memory, this heap can grow towards the upper end of your address space. As you can see, there is a potential for the heap to "collide" with the stack (a bit like tectonic plates!!!).

The common cause for a stack overflow is a bad recursive call. Typically, this is caused when your recursive functions doesn't have the correct termination condition, so it ends up calling itself forever. However, with GUI programming, it's possible to generate indirect recursion. For example, your app may be handling paint messages, and, whilst processing them, it may call a function that causes the system to send another paint message. Here you've not explicitly called yourself, but the OS/VM has done it for you.

To deal with them you'll need to examine your code. If you've got functions that call themselves then check that you've got a terminating condition. If you have then check than when calling the function you have at least modified one of the arguments, otherwise there'll be no visible change for the recursively called function and the terminating condition is useless.

If you've got no obvious recursive functions then check to see if you're calling any library functions that indirectly will cause your function to be called (like the implicit case above).

Courtesy: Link1

Example:  This is a demo example which i have used to get the StackOverflowError
Wrote a long run recursive method to sum up-to n numbers.

// Recursive function to find sum of numbers
fun sumOfNumbers(aVal:Int):Int {
    sum+=aVal;
    if (aVal == 0)
        return sum  
    else      
        return sumOfNumbers(aVal-1)
}
print(sumOfNumbers(3)) // 3+2+1=6  - This won't cause StackOverflowError
Output: 6

See, here we have used the smaller number, assume i trying to give a larger number (it may differ based on the system memory), While I'm testing with the below scenario got caught with the StackOverflowError at 1023...1050 (randomly).

print(sumOfNumbers(9000))  // 9000+8999+8998...  - This cause StackOverflowError

Hence, In order to avoid this kind of issue, kotlin provides an option called tailrec, we need to add this keyword before to the recursive method, the rest will taken care by the kotlin internally do the looping kind of approach and facilitates to provide us the solid & valid output with out any crash or error.

// Same Recursive function to find sum of numbers using tailrec 
tailrec fun sumOfNumbers(aVal:Int):Int {
    sum+=aVal;  
    if (aVal == 0)
        return sum  
    else      
        return sumOfNumbers(aVal-1)
}

print(sumOfNumbers(9000))   // The tailrec keyword take care of the app crash or SOF error.
Output: 040504500

Kotlin - Extension Vs Infix

Extension:
Kotlin, similar to Objective C (Categories) & C# Extension methods, here kotlin provides the ability to extend a class with new functionality without inheriting the class i.e. by using the Decorator design pattern. This is done via special declarations called extensions. Kotlin supports both extension functions and extension properties.

Infix Function:
In Simple, All Extension functions are not Infix, but every Infix method must to be extension function.

Criteria: 
0. Mandatory to have a params to the function,
1. Function does not accept more than one params.

// Definition: Extension function, here we have extending the checkCastMyVote from the String Class (In-Built Class).
// Here the function is used as an expression.

fun String.checkCastMyVote(name: String, age: Int) =
        if (age >= ELIGIBLE_YEAR) {
            "$this $name your age is $age, you are eligible to cast your vote"
        } else if (age in 0..17) {
            "$this $name you need to wait for ${ELIGIBLE_YEAR.minus(age)} more year(s)"
        } else {
            "$this $name, please provide the valid birth year (Given: $age)"
        }

// Calling a Extension Function: 
println("Mr.".checkCastMyVote("Ragavan", 23))  // Passing a params
println("Mr.".checkCastMyVote(age = 42, name = "Rajeevan"))  // Named functions


// Infix function definition
infix fun Int.getAge(yob: Int) =
        if (yob > 0) {
            this.minus(yob)
        } else {
            yob
        }

// Infix function call (no need to use dot or typical function calling syntax)
val CURRENT_YEAR=2017
var YEAR_OF_BIRTH=1988
var age = CURRENT_YEAR getAge YEAR_OF_BIRTH

Also, we can also apply & access this both extension and infix function to the user defined classes as well.

// Defining the class
class Guru {
    var name: String = ""
    fun isPassed(totalMark: Int) = if (totalMark > 35) "Passed" else "Failed"
}

// Defining the infix function.
infix fun Guru.isScholarshipEligibleMessage(totalMark: Int) =
        when (totalMark) {
            in 0..34 -> "No scholarship available for ${this.name} "
            in 35..50 ->
                "${this.name} Avail 50% Scholarship of amount"
            in 51..80 -> "${this.name} Avail 70% of Scholarship amount"
            in 81..100 -> "${this.name} Avail 85% of Scholarship amount"
            else -> "${this.name} Total Mark is invalid"
        }


// Calling the method
 var guru = Guru()
    guru.name = "Rajeev Menon"
    var totalMarks = 0 //38 //79 //85
    println("${guru.name} is ${guru.isPassed(totalMarks)}")
    println(guru isScholarshipEligibleMessage totalMarks)