Recursion

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

Notice that 6! = 6 * 5!, and that the number 1 is the final number in the multiplication sequence.

Let's implement factorial in Python:

1def factorial(num: int) -> int:
2    if num == 1:
3        return 1
4
5    return num * factorial(num - 1)
6
7print('6! = ', factorial(6))
8

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.