Recursion

Recursion is one of the basic programming principles to organize computations and data. Using recursion we can implement a large computation (or data structure) using smaller, self-similar, parts until the computation is so small so as to become trivial.

For example, let us think about computing the factorial function \(n!\). The factorial \(0!=1\) is easy to compute. For \(n\geq 1\) we observe that \(n!=n\cdot (n-1)!\) holds. In particular, to compute \(n!\) it suffices to have available \((n-1)!\) and multiply it by \(n\).

Thus the factorial function is self-similar and readily admits a recursive implementation:

def factorial(n: Int): Int = {
  require(n >= 0)
  if(n == 0) {
    1
  } else {
    n * factorial(n-1)
  }
}

At the console we witness that function indeed works as intended:

scala> factorial(0)
res: Int = 1

scala> factorial(1)
res: Int = 1

scala> factorial(2)
res: Int = 2

scala> factorial(3)
res: Int = 6

scala> factorial(4)
res: Int = 24

scala> factorial(5)
res: Int = 120

scala> factorial(6)
res: Int = 720

Similarly we could compute the sum of the nonnegative integers up to \(n\). Indeed, for \(n=0\) the sum is \(0\), and to sum the integers up to \(n\geq 1\) it suffices to add \(n\) and the sum up to \(n-1\):

def sumUpTo(n: Int): Int = {
  require(n >= 0)
  if(n == 0) {
    0
  } else {
    n + sumUpTo(n-1)
  }
}

Again we witness that the function works as intended:

scala> sumUpTo(1)
res: Int = 1

scala> sumUpTo(2)
res: Int = 3

scala> sumUpTo(100)
res: Int = 5050