# 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


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)

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