Recursion in Python Demystified
PYTHON PROGRAMMING
Simply put, a recursive function is a function that calls itself.
This may sound simple, but if you try to learn more, you're likely to find explanations of recursion that are not that simple. This is because the casual definition of recursion above doesn't go into any details, and to fully comprehend how recursion works, you need to know more than what this simple sentence conveys:
A recursive function is a function that calls itself.
Check out Wikipedia for example. Full of technical jargon, the explanation is far from simple, especially for beginning programmers without IT- or math-related education. It's difficult to imagine a beginner trying to implement their own recursive function based solely on such an explanation.
Even though some recursive functions may look quite simple at first glance, trying to implement your first recursive logic may occur very difficult. That can be a tough task because one needs to change one's thinking about problems.
Most data scientists see Programming tasks as a sequence of smaller steps that lead to a final solution. Since we're used to iteration, we can feel confused by these two entirely distinct logics: iteration and recursion.
In this article, I want to demonstrate that recursion doesn't have to be as intimidating as it may seem. It's not meant to be a technical deep dive into recursion. Instead, I'll focus on basic applications of recursion, highlighting its practical value in certain tasks. Understanding this logic can be beneficial – especially for data scientists, who need to work with various sorts of business and computational sorts of logic – and frankly, you can use recursion without knowing all of its technical intricacies.
We will analyze three simple recursive functions: one representing the so-called flat recursion pattern and two representing the nested recursion pattern. One of them will be probably the most often used recursion example, that is, calculating the factorial of a number. However, it is the other two that I think can help understand recursion the most – in fact, I wrote this article because I wanted to share these two functions, as I think they can be particularly useful when learning recursion.
Next time you want or need to implement a recursive function, you can recall these three examples, and hopefully they will help you out. Certainly, I cannot promise that you won't have any problems with recursion after reading this article, since it's a relatively difficult concept for those who haven't yet worked with this logic, using a lot of iteration instead. But it's good to start your journey towards understanding recursion with small steps, and this article can be your first small step.
Should you know recursion at all?
This is perhaps the most crucial question. Some consider recursion a great topic for… coding interviews. As Carlos Brown writes in his article on recursion in Python,
Perhaps you're right, recursion is only useful for a coding interview and otherwise FORGET IT.
To learn recursion to increase your chances in coding interviews is not actually that bad an idea: it would be sad to fail during your programming interview due to a lack of such knowledge. A data scientist unaware of how recursion works? How embarrassing…
Carlos adds,
However, I am of the opinion that learning different programming paradigms, and the way in which they parse problems, will ultimately make you a better data scientist/coder. Learning a new paradigm exposes you to new ways of thinking and different ways to structure your code.
That's more than true. Data scientists work with data, and they often work with algorithms that represent various sorts of logic – and you'd be extremely lucky to never have to think about recursive tasks. Besides, I have problems with imagining a senior data scientist who does not know what recursion is and how it works.
That said, recursion can be useful in more situations than coding interviews. Sometimes recursive tasks can be very simple, sometimes quite difficult. When they are simple, it should be relatively easy to implement them – and the resulting code will often be very elegant. Isn't it nice to write an elegant piece of code? But when a recursive task occurs to be very complex, perhaps it's better to spend time pondering how to translate its logic to iteration. The resulting implementation will usually be less elegant, but it can be significantly more performant.
In my coding practice, I have frequently come across recursive tasks related to analyzing nested Python objects. These were, for instance, nested dictionaries – today, we will analyze two such examples, both dealing with nested dictionaries.
I can give you a practical example from my Python experience. Recursion plays a key role in the implementation of the [rounder](https://github.com/nyggus/rounder) Python package:
I would like to invite you to analyze the code of the rounder package after reading this article. The package's round_object() function (and its several counterparts for different rounding types) works in a similar way to how we will use Recursion: it searches through a whole Python object for numerical values and rounds them using the rules provided by the user, ignoring non-numerical objects.
The rounder package shows that there are situations in which recursion can be both natural and useful. That's why it's good to know how recursion works – but also how to implement it. Who knows, maybe one day you will work on a task that will be recursive in nature? This was exactly the situation when I started thinking about implementing rounder: recursion is a natural way of thinking about the task it accomplishes. Don't you want to be ready for such a situation?
Implementation
Flat recursion
Below, you'll find a very simple recursive function. First, we'll analyze the task we are to accomplish and the code implementing it, and then we'll discuss the solution.
Imagine a dictionary dict[str, str]. It can be something like this:
d = {
"first": "This is the first sentence. Hello!",
"second": "This is the second sentence."
" The mid sentence.",
"third": "And this is the third and the last"
" sentence. Good bye!",
}We want to write a function that analyzes a value for a given key, so the user needs to provide the key (e.g., "first"). When the user does not provide the key, however, we want the function to analyze the values of all keys of the dictionary.
String analysis will be simple so that the function is not overcomplicated by things that are irrelevant for our discussion on recursion. Thus, the analysis will include only three elements:
- the length of a string
- the number of unique words in the string
- the number of whitespaces in the string
This is the function that performs this task:
import re
def summarize_flat(dict[str, str], key=https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None) -> https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None:
if key is https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None:
for k in d.keys(): # Flag 1
print(f"'{k}'")
summarize_flat(d, k)
return
# Flag 2
n_whitespaces = len(re.findall(r's', d[key]))
print(
f" length : {len(d[key])}",
f" unique words: {len(set(d[key]))}",
f" whitespaces : {n_whitespaces}",
sep="n"
)I'd normally name this function summarize, but we need to distinguish this one, which represents the flat recursion pattern, from the one we'll analyze later on, which will represent the nested recursion pattern.
First, let's use the function for the "first" key:
>>> summarize_flat(d, "first")
length : 34
unique words: 16
whitespaces : 5And now for all keys:
>>> summarize_flat(d)
'first'
length : 34
unique words: 16
whitespaces : 5
'second'
length : 46
unique words: 13
whitespaces : 7
'third'
length : 54
unique words: 19
whitespaces : 10Note:
- The function takes two arguments: a dictionary
d(required) andkey(optional, either string orhttps://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None). - If
keyishttps://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None, the function is called with no specific key. In this case, it iterates over all keys in the dictionary, usingd.keys()(Flag 1). For each key, the function prints the key and then calls itself recursively with the key as the newkeyargument:summarize_flat(d, key). - If
keyis nothttps://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None, the function is called with the key provided by the user (Flag 2). It prints out the results of the analysis of the string kept ind[key]. The analysis includes the length of the string, the number of unique words in the string, and the number of whitespace characters in the string.
Most recursive functions have their own specificity, resulting from the task a function is to perform. The summarize_flat() function is specific in the following way. When you provide key, say, summarize_flat(d, "mykey") does not work in a recursive way. It simply analyzes the string kept in d["mykey"]. However, when called with key=https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None, summarize_flat(d) runs in a recursive manner: in a loop, it calls itself for each key, so it prints the analysis for the value kept under each key. So, the function iterates over all keys in the dictionary and calls itself recursively for each key. This recursive behavior allows it to print the analysis for all values of the dictionary.
This design effectively utilizes a single function, eliminating the need for separate functions like summarize_key() and summarize(). Calling the former would correspond to calling summarize_flat(d, "mykey"), while calling the latter to calling summarize_flat(d). The latter function would iterate through the dictionary's keys, calling summarize_key() for each key.
Many recursive functions follow a different pattern: they call themselves repeatedly until the so-called base case (also called the stopping condition) is met. In such recursive functions, the base case serves as the termination point for the recursion. When this condition is met, the function stops calling itself and starts returning values back up the call stack. Such a design is called nested recursion.
Our function is recursive, too, but it represents a slightly different pattern. This is because when summarize_flat() is called with key=https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None, it calls itself with all keys of d, but these calls don't call summarize_flat() anymore. That's why we can call this recursion flat rather than nested .
Nested recursion
Now that we know how flat recursion works, let's consider nested recursion. It's a more complex pattern, since each subsequent call of the function can call itself again, and again, and again, thereby creating a call stack. Let me show this using a similar example to the one we used above.
Imagine that the dictionary d can be nested, meaning that its keys can be either strings or dictionaries of strings, like this one:
d2 = {
"first": {
"1a": "This is the first sentence. ",
"1b": "Hello!"},
"second": "This is the second sentence. The mid sentence.",
"third": {
"3a": "And this is the third and the last sentence.",
"3b": "Good bye!"},
}Note that it's not dict[str, str] anymore because the latter str can be a dictionary. In order to create a type hint for this dictionary, we need a recursive type:
from typing import Union
NestedDict = dict[str, Union[str, 'NestedDict']]NestedDict is a nested dictionary where the keys are strings, and the values are either strings or nested dictionaries. This is exactly the type we want our recursive function to work with.
Nevertheless, using this type complicate things. This is because Python doesn't enable you to check instances of parametrized generic types, such as NestedDict. In order to check if an object has this type, then, we cannot just use isinstance(); instead, we would have to implement our own function for this check – but this would not solve our problems. Since this is quite a complication that is not really related to recursion, in this article I will get rid of type hints for the nested-recursion function. We will talk about this issue some other day.
In d2, two out of three keys are dictionaries of and one is a string. The summarize_flat() function will crash for this dictionary:
>>> summarize_flat(d2)
'first'
Traceback (most recent call last):
File "", line 1, in
File "", line 5, in summarize_flat
File "", line 10, in summarize_flat
File "/usr/lib/python3.12/re/__init__.py", line 217, in findall
return _compile(pattern, flags).findall(string)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: expected string or bytes-like object, got 'dict' This is because summarize_flat() was designed to work with dict[str, str] dictionaries only. We need to revise the function so that it works with NestedDictionary dictionaries, that is, recursively in a nested fashion: when it finds that a value for a considered key (say, key) is a string, it analyzes it; but when this value is a dictionary, it calls itself for d[key].
This is the implementation without type-hints:
def summarize_nested(d, key=https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None):
if key is https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None:
for k in d.keys():
if isinstance(d[k], dict):
print("n", f"'{k}' is a dict:", sep="")
summarize_nested(d[k])
print()
else:
print(f"'{k}'")
summarize_nested(d, k)
return
if isinstance(d[key], dict):
print(f"'{key}' is a dict:")
summarize_nested(d[key])
return
whitespaces = len(re.findall(r's', d[key]))
print(
f" length : {len(d[key])}",
f" unique words: {len(set(d[key]))}",
f" whitespaces : {whitespaces}",
sep="n"
)It's not that easy anymore, is it? Let's break the function down into pieces and analyze it that way.
- The function first checks if
keyishttps://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None(Flag 1). If it is, it iterates over all the keys in the dictionaryd. For each key, if the corresponding value is a dictionary (Flag 2),summarize_nested()informs about it and recursively calls itself with the nested dictionary (d[key]). - If the value is not a dictionary but a string (
Flag 3), the function prints the key and callssummarize_nested()forkey, so it analyzes the string and prints its results. - If
keyis nothttps://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None, the function checks if the value kept under keykeyis a dictionary. If it is (Flag 4), the function prints a message about that and recursively calls itself with the nested dictionary (d[key]). Otherwise (Flag 5)— that is, whend[key]is a string, the function analyzes this string: this is the function's base case.
Again, it's a nested recursive pattern, meaning that if the function finds a value kept under key key, it calls itself for d[key]. If d[key] is a string, the function analyzes it, but if it's a dictionary, the function again calls itself for this dictionary.
Above, we have only one level of nesting, but the dictionaries, whether d or those nested inside, also can be nested, and so on. Let's consider the following example of a dictionary with two nesting levels:
d2 = {
"first": {
"1a": "This is the first sentence. ",
"1b": "Hello!"},
"second": "This is the second sentence. The mid sentence.",
"third": {
"3a": "And this is the third and the last sentence.",
"3b": "Good bye!"},
}And these are the results:
>>> summarize_nested(d2)
'first' is a dict:
'1a'
length : 28
unique words: 12
whitespaces : 5
'1b'
length : 6
unique words: 5
whitespaces : 0
'second'
length : 46
unique words: 13
whitespaces : 7
'third' is a dict:
'3a'
length : 44
unique words: 14
whitespaces : 8
'3b'
length : 9
unique words: 8
whitespaces : 1Now, let's use three nesting levels:
d3 = {
"first": {
"1a": "This is the first sentence. ",
"1b": "Hello!"},
"second": "This is the second sentence. The mid sentence.",
"third": {
"3a": {
"3a1": "And this is the third and the last sentence.",
"3a2": "(At least I think it is.)"
},
"3b": "Good bye!"},
}Our summarize_nested() function will work just fine for this dictionary:
>>> summarize_nested(d3)
'first' is a dict:
'1a'
length : 28
unique words: 12
whitespaces : 5
'1b'
length : 6
unique words: 5
whitespaces : 0
'second'
length : 46
unique words: 13
whitespaces : 7
'third' is a dict:
'3a' is a dict:
'3a1'
length : 44
unique words: 14
whitespaces : 8
'3a2'
length : 25
unique words: 15
whitespaces : 5
'3b'
length : 9
unique words: 8
whitespaces : 1The summarize_nested() function can recursively explore nested dictionaries to any depth required: this is how the nested recursion pattern works.
Exercise: Both functions won't work when any of the values are neither a dictionary or a string. Implement a function that simply omits such values instead of throwing an error.
Recursion functions with return values
Neither of the two functions we examined returns a value; instead, they print the output. This simplifies the functions' implementation, as capturing the output of a recursive function recursively can introduce additional complexities.
The most commonly used recursive task is probably implementing a function that calculates the factorial. This can be achieved as follows:
def factorial(n: int) -> int:
if n == 1 or n == 0:
return 1
else:
return (n * factorial(n - 1))Let's analyze it:
- The factorial of 0 and 1 is 1, so if n is 0 or 1, the function returns 1. This scenario serves as the base case for the recursion.
- For any other positive integer
n, the function recursively calls itself with the argumentn-1and then multiplies the result byn. This calculatesn!by recursively multiplying n with the factorial ofn-1.
The function begins with the value of n and decreases recursively until it reaches 1 – that is, until it calls factorial(1), which is the base case. It shows a common example of the nested recursion pattern: with each call, the function recursively invokes itself (for example, factorial(i) calls factorial(i-1)), until it reaches the base case.
Performance
Recursion often offers attractive solutions to computational problems, but due to the overhead of function calls and the risk of stack overflow, it doesn't have to be performant for large values of n. Calculation of factorials using iteration can be more performant. Let's check this out, using the [perftester](https://github.com/nyggus/perftester) module. You can read about such benchmarks here:
Here's our benchmarking code¹:
import perftester
from functools import partial
def factorial_recursion(n: int) -> int:
if n == 1 or n == 0:
return 1
else:
return n * factorial_recursion(n-1)
def factorial_iteration(n: int) -> int:
if n < 0:
return https://towardsdatascience.com/recursion-in-python-demystified-d3b3b28ba121/None
result = 1
for i in range(1, n+1):
result *= i
return result
if __name__ == "__main__":
for n in (5, 10, 20, 50):
number = int(10_000_000 / n)
bench = partial(
perftester.time_benchmark,
n=n,
Number=number
)
t_iteration = bench(factorial_iteration)
t_recursion = bench(factorial_recursion)
perftester.pp({
"n": n,
"ratio recursion to iteration":
t_recursion["min"] / t_iteration["min"],
"time iteration": t_iteration["min"],
"time recursion": t_recursion["min"],
})And here are the results I got on my Windows 10 machine of 12 GB of RAM, run in WSL 2:
{'n': 2,
'ratio recursion to iteration': 0.7756,
'time iteration': 3.755e-07,
'time recursion': 2.912e-07}
{'n': 3,
'ratio recursion to iteration': 0.9755,
'time iteration': 3.908e-07,
'time recursion': 3.812e-07}
{'n': 4,
'ratio recursion to iteration': 1.187,
'time iteration': 3.873e-07,
'time recursion': 4.597e-07}
{'n': 5,
'ratio recursion to iteration': 1.275,
'time iteration': 4.272e-07,
'time recursion': 5.448e-07}
{'n': 10,
'ratio recursion to iteration': 1.747,
'time iteration': 5.774e-07,
'time recursion': 1.009e-06}
{'n': 20,
'ratio recursion to iteration': 2.078,
'time iteration': 9.821e-07,
'time recursion': 2.041e-06}
{'n': 50,
'ratio recursion to iteration': 2.255,
'time iteration': 2.279e-06,
'time recursion': 5.138e-06}The times ("time iteration" and "time recursion") are mean times the two functions needed to run for given n, in seconds. The most informative, however, is the recursion-to-iteration ratio, which shows how many times recursion was slower than iteration.
For n equal to 2, iteration was actually slower. For n of 3, both functions yielded more or less the same results. Starting from n of 4, recursion was slower and the bigger n, the bigger the ratio.
Conclusion
It's worth knowing recursion because it's a natural solution to a variety computational problems. I hope the article helped you understand how recursion works.
Let's summarize the two recursion patterns we've analyzed:
- In flat recursion, a function calls itself, but the subsequent calls do not call the same function again. Since each call of the function leads to a single subsequent call, there's no nesting of function calls within each other
- In nested recursion, a function calls itself, and the subsequent calls may also call the same function again. This creates a nested structure of function calls, resulting in multiple layers of nested calls before the recursion terminates.
That's it. This article aimed to help you understand the complexities of recursive logic. Mastering recursion may still be challenging, but I hope you can now approach recursive problems with a better understanding of the underlying logic. It's an attractive tool, and recursive functions usually tend to be more elegant than their iterative counterparts.
However, don't forget about potential performance issues. Oftentimes, it's preferable to use iteration for two reasons: it can offer better performance and safety, as recursion can lead to stack overflow. Nevertheless, iteration might be slower in cases where recursion depth isn't too deep, as demonstrated in the factorial example. Hence, when performance matters for your recursive task, you should benchmark both approaches and choose the better one.
If you want to use type hints for a nested recursive functions, things can go wild. That's why we haven't implemented them. I didn't want to introduce this additional complexity, as it could distract us from recursion. We'll discuss this topic at another time, in a dedicated article on type hinting for nested recursive functions.
Footnotes
¹ I used partial functions in the analyzed code to enhance readability. As you can see in this code snippet:
for n in (5, 10, 20, 50):
number = int(10_000_000 / n)
bench = partial(
perftester.time_benchmark,
n=n,
Number=number
)
t_iteration = bench(factorial_iteration)
t_recursion = bench(factorial_recursion)Partial functions allow for fixing argument values, simplifying calls to the corresponding function. In our example, we fixed the default values of n and Number for the perftester.time_benchmark() function, making calls simpler:
# Original - repetitive
t_iteration = perftester.time_benchmark(
factorial_iteration,
n=n,
Number=number
)
t_recursion = perftester.time_benchmark(
factorial_recursion,
n=n,
Number=number
)
# Partial function - clearer
bench = partial(
perftester.time_benchmark,
n=n,
Number=number
)
t_iteration = bench(factorial_iteration)
t_recursion = bench(factorial_recursion)This way, both calls use bench() for factorial_iteration() and factorial_recursion(), highlighting the same approach to benchmark both functions.
There's more to partial functions, and we'll explore them further in a future article.
