###
Recursion
General

At a high level, recursion is when a function (or method) calls itself.
In recursion, we are breaking the problem down into similar sub-problems of the same form. Then the problems get so small that they are easy to solve.
There are two cases to a recursive function (or method): the base case and the recursive case.
The base case is the simplest form of the recursive problem. The base case can be immediately solved without breaking the problem down any further.
The recursive case is the general form of the recursive problem. In this case the problem needs to be broken down by one step toward the base case, and the algorithm makes a recursive call to itself to solve this slightly smaller problem. This process repeats until the base case is reached.
Recursion is very useful when a problem is best defined in terms of itself. For example this is the mathematical definition of the factorial of a positive number x:
factorial(x) = ...
* 1 if x is 0
* x * factorial(x - 1) otherwise
so we would define a function (or method) called factorial recursively as follows:
```
function factorial(x):
if x == 0:
return 1
else:
return x * factorial(x - 1)
```