Recursion is a computing pattern where a function solves a problem by breaking it down into subproblems and calling itself repeatedly until it solves them.
A recursive function includes a base case that it eventually reaches to stop further recursive calls. Without a base case, the recursive calls would never end, and we'd run into a stack overflow.
For example, let's take a look at computing the factorial of a number.
6! = 6 * 5 * 4 * 3 * 2 * 1
6! = 6 * 5!, and that the number
1is the final number in the multiplication sequence.
Let's implement factorial in Python:
Each time we call
factorial, we put the call on the stack. Eventually we hit our base case where
num = 1, and each function call on the stack can return.