Recursion is particularly useful for divide and conquer problems; however, it can be difficult to understand exactly what is happening, since each recursive call is itself spinning off other recursive calls. A recursive function can be in an infinite loop, therefore, it is required that each recursive function adhere to some properties. At the core of a recursive function are two types of cases:
- Base cases: These tell the recursion when to terminate, meaning the recursion will be stopped once the base condition is met
- Recursive cases: The function calls itself and we progress towards achieving the base criteria
A simple problem that naturally lends itself to a recursive solution is calculating factorials. The recursive factorial algorithm defines two cases: the base case when n is zero (the terminating condition), and the recursive case when n is...