Recursion

Recursion is used to implement recurring logic without relying on loops and the internal states associated with them. The recursive behavior is defined by two properties:

• Base case: The simplest terminating case, in which no recursive calls are needed anymore
• Recursive case: The set of rules describing how to reduce any other state to the base case

One of the possible examples for recursive implementation can be reversing a string. The two recursive properties would be:

• The base case is an empty or single-char string. In this case, the reversed string is just the same string as given.
• The recursive case for the string of length N can be reduced to the case of a string of length N-1 by taking the first char of the string and appending it to the reversed tail of the given string.

This is how we implement this logic in Scala:

def reverse(s: String): String = {
  if (s.length < 2) s
  else reverse(s.tail) + s.head
}

So, this is easier implemented than explained, right? 

One important aspect of our implementation in a recursive case is that it first makes the recursive call and then adds the rest of the string to the result. Such functions are head-recursive (but usually just called recursive) in the sense that the recursive call stays in the head of the computation. This works in a similar way to the depth-first algorithm, with the implementation first going down to the terminal case and then building up the result from the bottom up:

scala> println(reverse("Recursive function call"))
llac noitcnuf evisruceR

The nested function calls are naturally kept in the stack during runtime. Because of this, functions that work fine for inputs of smaller size might blow up the stack for bigger inputs, crashing the whole application:

scala> println(reverse("ABC" * 100000))
java.lang.StackOverflowError
  at scala.collection.StringOps$.slice$extension(StringOps.scala:548)
  at scala.collection.StringOps$.tail$extension(StringOps.scala:1026)
  at ch03.Recursion$.reverse(Recursion.scala:7)
  at ch03.Recursion$.reverse(Recursion.scala:7)
  at ch03.Recursion$.reverse(Recursion.scala:7)
  ...

It is possible to increase the size of memory reserved for a stack in JVM, but often there is a better solution—tail recursion.