🫀Anatomy of Recursion

What it looks like.

Let's consider a simple mathematical problem: Factorials. A factorial are the product of an integer and all the integers below it. That is

$$4! = 1.2.3.4 = 24$$

This definition gives us an important insight into the core mathematical concept behind factorials. That is this: the factorial of a number is the product between the number and the factorial of the decrement of that number.

$$n! = n \ * (n-1)!$$

We also know the smallest integer that has a factorial: zero.

$$0! = 1$$

With all these concepts combined, we can go ahead and write this in code.

def factorial(n):
    '''
    Accepts a non-negative number n and returns the factorial of that number.
    '''
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

All recursive questions have two halves: the base case and the recursive case. Here, the base case is n being equal to 0. All inputs to the function will end up at the base case eventually. The recursive case here is n * factorial(n-1). This is exactly what we'd written mathematically, in code form instead. A crucial part of the recursive case is the way a problem is becoming smaller: factorial(n-1) constantly decrements n to eventually reach the n==0 condition.

It is worth mentioning here that one can have multiple recursive and base cases. For simplicity, we stick to an example that only has one.

Let's walk through how factorial(4) is computed to see the full picture clearly.

= factorial(4) 
= 4 * factorial(3) 
= 4 * (3 * factorial(2)) 
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0)))) # Base Case!
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24

We've spent a bunch of this chapter seeing how recursion works behind the scenes. In the next section, we've talking about why you shouldn't do that. Yes, really.