Python Recursion: A Guide

How to Use Python Recursion

Python recursion is an intimidating topic for beginners. Let’s dispel the myth that recursion is difficult by defining it. Recursion is a method of programming where a function calls itself.

That sounds simple, right? When you get the hang of it, recursion is not a difficult concept.

In this Python tutorial, we’re going to talk about recursion and how it works. We’ll walk through an example of recursion using factorial functions to help you get started with this method of programming.

What is Recursion?

Recursion is where you define something in terms of itself.

A recursive function solves problems by calling itself over again. This behavior is supported in most major programming languages, such as Python. They are a crucial part of computer science and data science.

Recursion is useful when the solution to a problem can be found by breaking it down into smaller problems which all use the same formula. These types of problems are often called “recursive algorithms.” The key to solving them is in the name!

Iterative vs. Recursive

There are two ways to solve an algorithm: iteratively or recursively.

Iterative solutions to algorithms are regarded as “powerful but ugly.” They get the job done, but they don’t exactly do it in the most elegant way. To properly understand recursive algorithms, we need to look at iterative functions.

An iterative function is a function that solves a problem using a loop. It will execute the code inside a loop until that loop is complete. A recursive function is a function that breaks a problem down into smaller parts and solves each part by calling itself.

Factorials: The Iterative Example

Factorials are a good way to demonstrate recursion and iterative thinking. In math, factorials are the sum of a number and every number before it multiplied together.

The factorial of 5 is equal to 5 * 4 * 3 * 2 * 1. The factorial of 2 is equal to 2 * 1.

To calculate a factorial, we can write an iterative function:

def factorial(number):
	total = 1
	for n in range(1, number + 1):
		total = total * n
	return total

This function uses a for loop to iterate through all numbers in the range of 1 and the number we have specified plus 1. For each iteration, the number the loop is iterating over is multiplied by the total. Let’s call our function to find the factorial:

answer = factorial(4)
print(answer)

Our code returns: 24. To arrive at this solution, our code runs:

• 1 * 1 = 1
• 2 * 2 = 4
• 4 * 3 = 8
• 8 * 4 = 24

As you can see, our code multiplies 4 with all the numbers lower than it and then itself.

This code is functional. The only drawback is that it’s not as elegant as it could be. That’s where recursive functions come in handy.

Factorials: The Recursion Example

Let’s write a recursive function that calculates a factorial. Open up a new Python file and paste in the following code:

def factorial(number):
	if number == 1:
		return 1
	else:
		return (number * factorial(number - 1))

This code uses the recursive approach. When this function is run, an ”if” statement is executed. This statement checks whether the number passed to the function is equal to 1. If it is, our function returns 1. Otherwise, the factorial of our number is calculated.

This calculation works by multiplying the number passed to the function by the factorial of the previous number. This function is called again and again until “number” is equal to 1. Each time the function is called, the value of “number” is reduced by 1.

Let’s give our code a try with the number 4:

answer = factorial(4)
print(answer)

The answer 24 is returned. Our answer is correct; it’s the same as our last example. We have found the solution to this problem recursively instead of iteratively.

Do you still need a little bit of help? Let’s walk through another example of recursion.

Recursion with the Fibonacci Sequence

The fibonacci sequence is a mathematical sequence where each number is the sum of the two previous numbers. This sequence starts with: 0, 1, 1, 2, 3, 5, 8, 13, and so on.

This sequence adds two numbers to find the next number. This makes it ideal for recursion.

Open up a Python file and paste in this code:

def fibonacci(number):
	if number <= 1:
		return number
	else:
		return(fibonacci(number - 1) + fibonacci(number - 2))

This code will calculate the sum of two preceding numbers in a list, as long as “number” is more than 1. Otherwise, “number is returned”. Now, let’s call our function:

executions = 5

print("Fibonacci Sequence:")
for number in range(executions):
	print(fibonacci(number))

The executions variable tracks how many numbers in the fibonacci sequence we want to calculate. We use this to create a for loop which calls our fibonacci() function for each number in the range of 1 and the value of “executions.”

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

Before our for loop starts, we print “Fibonacci Sequence:” to the console. In this example, our “for” loop executes:

fibonacci(1)
fibonacci(2)
fibonacci(3)
fibonacci(4)
fibonacci(5)

Let’s run our code all together and see what happens:

Fibonacci Sequence:
0
1
1
2
3

Our code calculates the first five numbers in the fibonacci sequence. We could calculate more numbers by increasing the value of “executions”.

Recursion Depth and Base Conditions

A recursive function must have a base condition. This is a condition that stops the recursion when a particular base case is met. Without a base function, an infinite loop will be created.

A recursive function can execute itself no more than 1,000 times by default. Once this limit is reached, an error like this appears:

RecursionError: maximum recursion depth exceeded

Here is the base condition for our fibonacci program:

...
if number <= 1:
		return number
…

This condition checks if the value of “number” inside our fibonacci program is equal to or less than 1. If it is, the value of “number” is returned; otherwise, the recursive function starts.

Why Should I Use Recursion?

What’s the advantage of using recursion over iterative functions? Technically, both methods can accomplish the same result. The benefit of recursion is that it is easier to read.

When you see a recursive function, it’s clear that the answer to a problem lies in breaking it down into smaller parts. While iterative loops can sometimes be quicker, recursive functions are usually preferred due to their readability.

Because recursive functions are easier to read, they are also easier to maintain and debug. This is especially useful when you are writing complex algorithms that may be difficult to understand.

Conclusion

A recursive function is a function that calls itself to find the solution to a problem. 

Recursive functions break down a problem into multiple parts and solves one part of the problem per iteration. Recursive functions are commonly used to calculate factorials and numbers in the fibonacci sequence. They’re also used in a number of algorithms.

Now you’re ready to start working with recursive functions in Python.