Recursion

Recursion is one of the basic programming principles used 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, and we call this the base case.

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\). We call this the recursive step.

Thinking about the above, we might realise that if we want to find out the factorial for some value \(n\) that is not the easy to answer base case, we know how to make the answer just a little bit easier: by calculating the factorial value for \(n-1\) first. If we keep doing this we will eventually come to the base case, by which time we can start constructing the answer by multiplying numbers.

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

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

As you can see the functions factorial calls itself on line 6 in the listing above. This is perfectly fine. It just means that during execution we need to find out the value of that call before we can complete the current calculation. Because we decrease n every time factorial is called by itself, we know that for any \(n>0\) we will eventually hit the base case n == 0.

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 then
    0
  else
    n + sumUpTo(n-1)
  end if
end sumUpTo

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

We will come back to recursion later in the course and revisit the topic in more detail.

Think about this

If you try to compute the factorial of a larger number, for example 40, using factorial as declared above, you will see a perhaps unexpected result:

scala> factorial(40)
val res: Int = 0

Is this correct, and if not, why do we get that result?

Try to replace the parameter and result type of Int with Long. What happens now? Why?