# Recursion

Recursion occurs when a function calls **itself**. Recursion is useful when dealing with problems that have recursive properties. Consider a function **factorial(n)** that returns the factorial of **n**. This function can be defined recursively because **factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) **and so on.

Thus, when defining this function you might be tempted to do something like this:

However, this function will not work because the function will keep calling itself forever; it will not know when to stop. Therefore, to define a recursive function, you must define a **base case** that tells the function when to stop calling itself. In **factorial()**, you can define a base case to be **factorial(0)** that returns **1**, not further calling **factorial(-1)**.

The above function will now work correctly. Let’s look at how and why **factorial() **works in detail.

Suppose you call **factorial(3)**. Here is how your computer’s stack will look like:

When you call **factorial(3)**, it returns **3 * factorial(2)**. **factorial(3) **waits in the stack while your program calls **factorial(2)**.

**factorial(2)** returns **2 * factorial(1)**. Again, your program calls **factorial(1)** while **factorial(2)** is waiting in the stack.

**factorial(1)** returns **1 * factorial(0)**. Again, your program calls **factorial(0)**, while **factorial(1)** waits in the stack.

**factorial(0)** return **1**, which is the base case we defined. Now, **factorial(1)** can be evaluated to be **1**. Again, **factorial(2)** can be now evaluated to be **2 * 1**, and so on. Finally, **factorial(3)** can be evaluated to be **3 * 2**, which is **6**.