# Recursion

Recursion is where a single *function* inside a computer program calls itself.
This turns out to be an extremely versatile tool in the computer science
toolbox. Consider the following toy example where we can use recursion to
solve factorials.

The solution to *n*! is *n*×*n*-1×*n*-2×*n*-3×…×1. For example the solution to
5! is 5×4×3×2 = 120. Notice that we can also arrive at this solution by
multiplying 4! by 5, we can arrive at 4! by multiplying 3! by 4, and so on.

We can therefore write a recursive function that calls itself called `factorial`

:

```
factorial(n):
(n - 1)! = factorial(n - 1)
n! = (n - 1)! × n
return n!
```

What’s wrong with the above function? It will never stop calling itself! Consider if
we made the function call `factorial(5)`

:

```
factorial(5):
(5 - 1)! = factorial(4):
(4 - 1)! = factorial(3):
(3 - 1)! = factorial(2):
(2 - 1!) = factorial(1):
(1 - 1!) = factorial(0):
(0 - 1!) = factorial(-1):
...
```

To make it work, we can add a conditional `if...else`

statement (also known as
branching) inside the recursive function. We know that the value of 1! is 1, so
when factorial(1) is called, let’s simply set n! to 1.

```
factorial(n):
if n == 1:
n! = 1
else:
(n - 1)! = factorial(n - 1)
n! = (n - 1)! × n
return n!
```

When the function is called, the recursion will now proceed downwards to
factorial(1), then back upwards via the return statements. Again imagine we
call `factorial(5)`

(hereafter `f(n)`

). This will create a cascade of
recursion where the function calls where `f(5)`

calls `f(4)`

, which calls
`f(3)`

, which calls `f(2)`

, which finally calls `f(1)`

. Then, `f(2)`

will
return 1, `f(2)`

will return 2, `f(3)`

will return 6, `f(4)`

returns 24, then
finally `f(5)`

returns the final value of 120:

Now you know how to use recursion!