Scala recursion demo -Normal (java style recursion ) as well as tail recursion

Why Tail Recursion?

In the recursion 1st example below, notice how the result of each call must be remembered, to do this each recursive call requires an entry on the stack until all recursive calls have been made. This makes the recursive call more expensive in terms of memory.

While in the tail recursive 2nd and 3rd example, there are no intermediate values that need to be stored on the stack, the intermediate value is always passed back as a parameter.

Importance of tail recursion in Spark-Kryo stand point : In Spark with Kryo Serialization for Very large object graphs produces StackOverflowError to avoid this first option we need to consider tail recursion for such scenarios. second option is increasing -XSS refer my SO answer .

Note :

1. Comments were added inline with code as explanation.
2. Tested in Worksheet mode

/**
  * Normal recursion which is like Java/anyother programming language style
  **/
def sumNormalRecursion(xs: List[Int]): Int = xs match {
  case Nil => 0
  case head :: tail => head + sumNormalRecursion(tail)
}
println("Normal recursion if data is heavy then Stackoverflowerror in java also " + sumNormalRecursion(List(1, 2, 3)))

// NOTE : Compiled with scala 2.12 @tailrec annotation is not required
/**
  * tailrec with List of Int There is no chance of stackoverflow error since tail is added only one value 
  * at stack frame so there is no danger
  **/
def sumtailrecOfInt(xs: List[Int]): Int = {
  def tailrec(xs: List[Int], accumulator: Int): Int = {
    xs match {
      case Nil => accumulator
      case head :: tail => tailrec(tail, accumulator + head)
    }
  }
  tailrec(xs, 0)
}
println("Tail recursion with List of Integers " + sumtailrecOfInt(List(1, 2, 3)))
/**
  * Tail rec with List of Double  There is no chance of stackoverflow error since tail is added only one value 
  * at stack frame so there is no danger
  **/
def sumOfDoublesTailrec(xs: List[Double]): Double = {
  def tailer(xs: List[Double], acc: Double): Double = {
    xs match {
      case Nil => acc
      case head :: tail => tailer(tail, acc + head)
    }
  }
  tailer(xs, 0.0)

}
println("Tail recursion with List of Double " + sumOfDoublesTailrec(List(1.0, 2.0, 3.0)))

Similarly factorial example normal recursion :

def factorial(number:Int) : Int = {
    if (number == 1)
       return 1
number * factorial (number - 1)

}
println(factorial(5))

Tail recursive version of factorial Version 1(with out using nested method)

def factorial(accumulator: Int, number: Int) : Int = {
  if(number == 1)
    return accumulator
  factorial(number * accumulator, number - 1)
}
println(factorial(1,5))

Tail recursive version of factorial Version 2(with nested method)

def factorial(x: Int): Int = {
    def fact(x: Int, accumulator: Int): Int = {
      if (x <= 1) accumulator
      else fact(x - 1, x * accumulator)
    }  
    fact(x, 1)
 }
println("Factorial of 2: " + factorial(2))
println("Factorial of 3: " + factorial(3))

Output : Factorial of 2: 2 . Factorial of 3: 6

Use Case retry : Another good use case of Tail recursion is retry. Below function will retry 3 times after 30 seconds and then throws exception. This is one of the common scenario in programming.

// No exception this will just print message

retry(3) { println(" Hi Ram! ONMGPN") } 
// below code exception will be thrown and will try the same for 3 times hence 3 times message will be printed
retry 3 times when exception happened other wise print the message
retry(3) { println("Hi Ram! ONMGPN")   throw new RuntimeException("Test recursive retry")  }

/**
Retry for 3 times when any exception occurs, otherwise below will execute only once.
**/
def retry[T](n: Int = 3)(fn: => T): T = {
    util.Try {
      fn
    } match {
      case util.Success(x) => x
      case util.Failure(e) => if( n > 1) {
        Thread.sleep(3000) //30 seconds
        retry(n - 1)(fn)
      }
      else throw e
    }
  }

 This kind of logic is really useful when job A is updating database table A and job b is trying to read and do processing further from table A. in no data found case, it will throw exception. Instead of simply coming out with an exception, it will retry for 3 times with a delay of 30 seconds latency. If all 3 attempts were failed then it will throw exception.