# Recursion and Recursive Functions in Python

**Python hosting**: Host, run, and code Python in the cloud!

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:**

Python Programming Bootcamp: Go from zero to hero

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

**Related Course:**

Python Programming Bootcamp: Go from zero to hero

Leave a Reply:Thanks for the Tutorial!

Thanks Harm! More tutorials coming soon

That's a big number :o,

Thanks for the Tutorials you helped me a lot!

Thanks! More tutorials coming soon

Thanks a lot. I'm looking forward to more tutorials.

In the second example on line 7 it says:

return list[0] + sum(list[1:])

What does "[1:]" do? I looked and didn't see anything about that elsewhere in the tutorials.

Hi Christian, [1:] returns everything from the second character.

I want to say thank you for your awesome tutorial. thank you. :)

Thanks Fin!

I agree with Fin. Thanks a lot for putting together this tutorial which is simple to grasp and not boring unlike the vast majority of the tutorials