Recursion in Python (39/100 Days of Python)

Day 39 of the “100 Days of Python” blog post series covering recursive functions

Recursive functions are a powerful tool in Python that allow you to solve problems by breaking them down into smaller, manageable sub-problems. In this tutorial, we will explore what recursive functions are, when they are useful, and how to use them effectively in your own Python code.

What are Recursive Functions in Python?

A recursive function is a function that calls itself in its definition. This allows the function to repeat its actions until a specific condition is met. The key to understanding recursive functions is to understand the concept of recursion. Recursion is a technique for solving problems by breaking them down into smaller, more manageable sub-problems:

def print_numbers(n):
    if n == 0:
        return
    print(n)
    print_numbers(n-1)

In this example, the print_numbers function takes an argument n and prints the numbers from n to 1. The function checks if n is equal to 0. If n is equal to 0, the function execution stops. If n is not equal to 0, the function prints the value of n and then calls itself with n-1. This continues until n is equal to 0 and the function returns. So, if we call print_numbers(5), it will print 5 4 3 2 1 each on a separate line.

When are Recursive Functions Useful in Python?

Recursive functions are useful in a variety of different contexts. One common use case for recursive functions is when you need to perform a complex calculation on a nested structure. A great example is traversing data structures like trees or lists. For example, you could use a recursive function to traverse a tree structure and find all of the leaf nodes.

Using Recursive Functions in Python

Using recursive functions in Python is actually quite straightforward. The basic idea is to create a function that calls itself until a specific condition is met. As an example, let’s calculate the factorial of n.

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

In this example, the factorial function calculates the factorial of a number. The function takes one argument, n, and checks to see if n is equal to zero. If n is zero, the function returns 1. If n is not zero, the function returns n multiplied by the factorial of n-1. This is the recursive step, where the function calls itself with a smaller value for n until n is equal to zero.

It is important to note that every recursive function needs to have a base case, which is the condition that stops the recursion. Otherwise, the code will execute forever. In our example, the base case is when n is equal to zero.

If we forget to have a condition for stopping, we might end up with an infinitely running code or a stack overflow (which we will discuss soon):

def print_numbers(n):
    print(n)
    print_numbers(n-1)

This function will print numbers infinitely as it will never reach a stopping point.

Tips for Effective Recursive Function Usage

When using recursive functions in Python, it is important to keep the following tips in mind:

1. Make sure that the base case is well-defined and will stop the recursion at some point. Otherwise, the code might end up running forever.
2. Make sure that the recursive step gets closer to the base case each time the function is called.
3. Keep the number of recursive calls to a minimum to avoid stack overflow errors.

What’s next?

• If you found this story valuable, please consider clapping multiple times (this really helps a lot!)
• Hands-on Practice: Recursion
• Full series: 100 Days of Python
• Previous topic: Does Python Have Pass-by-Value VS Pass-by-Reference Variables?
• Next topic: What is Stack Overflow Really?