# Tag: recursion

## Recursion

In English there are many examples of recursion:

- "To understand recursion, you must first understand recursion",
- "A human is someone whose mother is human".

You might wonder, what does this have to do with programming?

You may want to split a complex problem into several smaller ones. You are already familiar with loops or iterations. In some situations recursion may be a better solution.

In Python, **a function is recursive if it calls itself and has a termination condition**. Why a termination condition? To stop the function from calling itself ad infinity.

**Related Course:**

Complete Python Bootcamp: Go from zero to hero in Python 3

## Recursion examples

**Recursion in with a list**

Let’s start with a very basic example: adding all numbers in a list. Without recursion, this could be:

#!/usr/bin/env python |

Where we simply call the sum function, the function adds every element to the variable sum and returns. To do this recursively:

#!/usr/bin/env python |

If the length of the list is one it returns the list (the termination condition). Else, it returns the element and a call to the function sum() minus one element of the list. If all calls are executed, it returns reaches the termination condition and returns the answer.

**Factorial with recursion**

The mathematical definition of factorial is: n! = n * (n-1)!, if n > 1 and f(1) = 1. Example: 3! = 3 x 2 x 1 = 6. We can implement this in Python using a recursive function:

#!/usr/bin/env python |

When calling the factorial function n = 3. Thus it returns n * factorial(n-1). This process will continue until n = 1. If n==1 is reached, it will return the result.

## Limitations of recursions

Everytime a function calls itself and stores some memory. Thus, a recursive function could hold much more memory than a traditional function. Python stops the function calls after a depth of 1000 calls. If you run this example:

#!/usr/bin/env python |

You will get the error:

RuntimeError: maximum recursion depth exceeded |

In other programming languages, your program could simply crash. You can resolve this by modifying the number of recursion calls such as:

#!/usr/bin/env python |

but keep in mind there is still a limit to the input for the factorial function. For this reason, you should use recursion wisely. As you learned now for the factorial problem, a recursive function is not the best solution. For other problems such as traversing a directory, recursion may be a good solution.