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: Object Oriented Programming

## 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 def sum(list): sum = 0 # Add every number in the list. for i in range(0, len(list)): sum = sum + list[i] # Return the sum. return sum print(sum([5,7,3,8,10])) |

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 def sum(list): if len(list) == 1: return list[0] else: return list[0] + sum(list[1:]) print(sum([5,7,3,8,10])) |

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 def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print factorial(3) |

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 def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print factorial(3000) |

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 import sys sys.setrecursionlimit(5000) def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) print factorial(3000) |

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.

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

I want to say thank you for your awesome tutorial. thank you. 🙂

Thanks Fin!

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.

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

That’s a big number :o,

Thanks for the Tutorials you helped me a lot!

Thanks! More tutorials coming soon

Thanks for the Tutorial!

Thanks Harm! More tutorials coming soon