Recursion in Python

You've already learned the theory behind recursion. In this topic, we will put this knowledge to practice by learning how to write recursive functions. To make sure that we are on the same page, let's remind ourselves of the definition of recursion.

Recursion is a method of solving problems by breaking them down into smaller instances. The solutions to those sub-problems are then combined into a bigger solution to the original problem.

Parts of a recursive function

In programming, recursion is achieved when a function calls itself from its code. Sounds simple, doesn't it?

The main function can generally do only two things: either perform a simple task and return a value or call itself with new arguments to divide the problem into smaller chunks. Let's consider an example. Suppose you want to find out the number of people sitting to your left in a long row of seats. You can ask a person to your left how many people are sitting to their left. That person then asks a person to their left, that person asks a new person on the left, and so forth. The process of asking the question is a recursive case (a recursive action). As a result, each person gets the number, adds 1, and passes the message further.

If you're going to use a recursive function in your program, you'll have to terminate it at some point. Otherwise, it may lead to an infinite loop. A condition that stops a recursion is called the base case. In our example, the recursion will end when a person occupying the leftmost seat says, "no one".

To summarize, there are two obligatory steps in each recursive function:

1. A base case that works as a stop sign. It is the smallest problem that can be solved without any further subdivision. It is a condition where a function only outputs a result;

2. A recursive case (also called a reduction step) is the part where the function calls itself to try and solve a smaller problem.

Constructing a recursive function

Let's construct a recursive function for finding the factorial of an integer number in Python. It looks like this:

$5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 * 0! = 5 * 4 * 3 * 2 * 1 * 1$

This means that we can calculate the factorial of a number by multiplying this number by the factorial of the previous number:

$N! = N * (N-1)!$

Now, to write a recursive function, we need to define the recursive and the base cases.

As for the recursive case, we need to define a step where we're trying to find the solution to the simpler instances of our problem. With the factorial of $n$, this would infer multiplying $n$ by the factorial of $n-1$:

def recursive_factorial(n):
    # recursive case
    return n * recursive_factorial(n - 1)

As for the base case, to prevent our function from calling itself infinitely, we need to set the stop rule or reduce the solution to the smallest possible problem. In our case, the simplest problem is $0!$

def recursive_factorial(n):
    # base case
    if n == 0:
        return 1
    # recursive case
    else:
        return n * recursive_factorial(n - 1)

This is the typical structure of any recursive algorithm. If a problem is reduced to a simple case, solve it. If not, divide it into subproblems and apply the same strategy.

Maximum recursion depth

By now, we've noted that recursion is a function that calls itself. Of course, it tends to occupy the resources of your machine. Like any other function, a recursive function operates with memory, so to prevent it from crashing, Python limits the maximum number of callings — this parameter is called the recursion depth. When it goes beyond the limit, you'll get RecursionError: maximum recursion depth exceeded. This is how you can check the recursion depth:

import sys  # allows manipulation of Python interpreter

recursion_limit = sys.getrecursionlimit()
print(recursion_limit)  # 1000

If we go back to the structure of a recursive function, it means that even if the base case isn't defined, you won't be able to execute your program forever. When the maximum recursion depth is exceeded, you'll get an error.

You can change this parameter manually:

sys.setrecursionlimit(1500)
new_limit = sys.getrecursionlimit()
print(new_limit)  # 1500

Be careful with this option, as it influences the memory use of your program.

Recursion tracing

Since the concept of recursion may be daunting at first, it is a good idea to visualize the function execution manually or automatically to trace it and have a more clear picture of how it works. Look at the function below:

def func(x, y):
    # base case
    if x < y:
        return x
    # recursive case
    else:
        return func(x - y, y)
	
print(func(20, 5))  # 0

Here's what it does. The function takes two numbers. In case the first one (x) is less than the second one (y), the function returns x, and the execution stops. This is our base case. Otherwise, the function is called recursively, but at each iteration x is decreased by y until the first condition (x is less than y) is met. Let's visualize it manually step by step:

func(20, 5) -> func(15, 5)
   func(15, 5) -> func(10, 5)
     func(10, 5) -> func(5, 5)
       func(5, 5) -> func(0, 5)
         func(0, 5) -> 0        # this is our base case
       func(5, 5) -> 0          # we're going back since these calls don't return anything useful        
     func(10, 5) -> 0
   func(15, 5) -> 0
func(20, 5) -> 0                # the final answer

You can also try automatic visualization. Just run it!

Recursion vs. Loops

Reading about recursion, you may have noticed that the cases we can solve with recursion are similar to ones solvable with loops. An important thing here is that they have different purposes (loops are designed to repeat a task; recursion is meant to break down a larger task into smaller ones), but recursion and loops are quite similar. Moreover, if we're solving a problem using recursion, we can also solve it with loops. Sometimes it is easier to solve a problem using recursion because the solution is brief and clear, sometimes the performance is crucial, so you may consider a less elegant but more efficient iterative algorithm. At the end of the day, it's really up to you.

To illustrate this idea, let's implement two functions; both will calculate the power. We will use the first one as an iterative implementation:

def pow_iter(number, power):  # iterative
    
    result = 1
    
    for i in range(power):
        result = result * number
    
    return result
    
print(pow_iter(5, 2))  # 25

While the second one is recursive:

def pow_rec(number, power):  # recursive

    if power == 0:
        return 1

    return number * pow_rec(number, power - 1)
	
print(pow_rec(5, 2))  # 25

As you can see, both functions do the same thing; you can choose the solution depending on which one uses less memory, is faster and clearer. Citing the explanation by Leigh Caldwell on Stack Overflow — Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!

Conclusion

Here's what we've learned in this topic:

• What recursion is and how to construct a recursive function;

• What the notion of the maximum recursion depth is, and why we need it;

• How to manually and automatically trace recursive functions for better understanding;

• The difference between recursive and iterative implementations, which one to choose, and why.

Summing up, recursion can seem to be mean at first, but it is one of the most important skills in any programmer's toolkit. There are cases where it can be amazingly helpful.