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,
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
Long. What happens now?