Recursion ReviewΒΆ
Recursion is the concept of defining something by breaking it into similar, but smaller or simpler pieces. These smaller or simpler pieces are defined in the same way as the larger piece. Because of this, the definition “folds” or “wraps” in upon itself.
For example, consider the calculation of factorial. The factorial of an integer is the product of itself and each of the smaller integers, down to one. For instance:
We could write a loop to evaluate factorial:
def fact(n):
rv = 1
for k in range(1,n+1):
rv = rv * k
return rv
This is a non-recursive version of factorial.
But, we could also observe that we can break the calculation of factorial into a smaller case and then extend the result of the smaller case to the bigger one. In particular:
This allows us to write a recursive version, a version where the function calls itself:
def fact(n):
if n == 1:
return 1
return n*fact(n-1)
The last line is said to be the recursive case: the case where we call the same function again, but with a smaller input. The first case, the case where we are calculating the factorial of the number one, is called the base case, analogously to the base case in a proof by induction. This case is an exception to the general rule modeled by the recursive case. We do not want to calculate the factorial of one by referring to the factorial of a smaller number and possibly continuing the recursion down into the negative numbers. Instead, we want to define the value for this input as a hard-coded value with no further function calls.
Base cases are essential in recursion. They keep our function from calling itself over and over again indefinitely. If we are missing a base case, not only do we not get the correct answer, but we likely get no answer at all as the program attempts to recurse infinitely. When a recursive programs crashes or fails to complete a calculation, a missing base case is the likely culprit.