🫀

# 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.

Last modified 1yr ago