# Anatomy of Recursion

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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://calnotes.gitbook.io/cs61a-guidebook/structures-of-data/recursion/anatomy-of-recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.