> For the complete documentation index, see [llms.txt](https://calnotes.gitbook.io/cs61a-guidebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://calnotes.gitbook.io/cs61a-guidebook/structures-of-data/recursion/anatomy-of-recursion.md).

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

```python
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.

```python
= 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.