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 then
    1
  else
    n * factorial(n-1)
  end if
end factorial

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

Think about this

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

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

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

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