Recursion in Scala: An Introduction

Hello, fellow explorer! Today, we will unravel the mystery of "Recursion" — a concept as enthralling as the patterns formed by two mirrors facing each other. Our aim is to decipher recursion, understand its inner workings, and master its application in Scala.

Consider a stack of books. Want the bottom one? You'll need to remove each book above it, one by one. It's a repeated action — an example of recursion. In programming, recursion involves a function calling itself repeatedly until a specific condition is met, similar to descending stairs one step at a time until you reach the ground.

Here's a simple Scala function illustrating recursion:

object RecursionExample {
  def recursiveFunction(x: Int): Unit = {
    if (x <= 0) { // Termination condition --> base case
      println("Base case reached")
    } else {
      print(x)
      recursiveFunction(x - 1) // Recursive function call --> recursive case
    }
  }

  def main(args: Array[String]): Unit = {
    recursiveFunction(5)
  }
}
/*Output:
5
4
3
2
1
Base case reached
*/

This function keeps calling itself with x getting lower by one until x <= 0, which is our base case. At this point, it stops the recursion.

The base case acts as a friendly signpost, indicating when the recursion should stop. In our book stack example, reaching a point where no more books are left to remove serves as the signal. Similarly, x <= 0 is our base case in our function. The base case is crucial as it prevents infinite recursion and related errors.

The recursive case is an essential part of recursion — the rule responsible for creating smaller versions of the original problem. Each call brings us a step closer to the base case. Let's use the process of calculating a factorial as an illustrative example.

To find a factorial, we multiply a number by the factorial of the number minus one and repeat this process until we get to one (our base case):

object FactorialExample {
  def factorial(n: Int): Int = {
    if (n < 0)
      throw new IllegalArgumentException("Negative numbers are not allowed!")
    if (n == 1 || n == 0) // base case
      1
    else
      n * factorial(n - 1) // recursive case
  }

  def main(args: Array[String]): Unit = {
    println(factorial(3)) // we expect 6 (3 * 2 * 1)
  }
}

In this case, when we call factorial(3), it returns 3 * factorial(2), where factorial(2) returns 2 * factorial(1). As factorial(1) is a base case, it returns 1. As a result, the whole recursion chain returns 3 * 2 * 1.

Note the input validation at the beginning — without it, calling factorial(-3) would cause infinite recursion since negative numbers would never reach our base case, leading to a stack overflow error.