python logo

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

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.

Related Course:
Python Programming Bootcamp: Go from zero to hero

BackNext





Leave a Reply:




Harm Mon, 15 Jun 2015

Thanks for the Tutorial!

Frank Tue, 16 Jun 2015

Thanks Harm! More tutorials coming soon

Aj Tue, 23 Jun 2015

That's a big number :o,
Thanks for the Tutorials you helped me a lot!

Frank Tue, 23 Jun 2015

Thanks! More tutorials coming soon

John Youn Wed, 24 Jun 2015

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

Christian Ransom Sun, 26 Jul 2015

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.

Frank Sun, 26 Jul 2015

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

Fin Mon, 07 Sep 2015

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

Frank Mon, 07 Sep 2015

Thanks Fin!

Fred Pouyet Thu, 17 Sep 2015

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