Introduction to Python. Part 12. Recursion

What is recursion and how it works - we show with examples

In this Workshop lesson we will talk about recursion. This is a programming technique where a function calls itself.

In order for recursion to work, two problems need to be solved. First, you need to find the base case, that is, the case when the function terminates. Secondly, we need to break down our problem that we want to solve using recursion into many small sub-problems; and if we can find a solution to a sub-problem, then we have solved the whole problem.

Problem 1

Let's try to understand recursion using a very simple example. Let's say we have a string and we want to print all its letters. To do this we need the following function:

Let's break down each line of code to better understand what's going on. First we need to decide on the base case. And for this task, the function must complete its work when it is passed an empty string. It’s logical: if there are no letters, then there’s nothing to print. And we describe this base case in this line of code: if not text: return. Notice that we're using the return keyword, but we're not returning anything—it's just an "Exit" command for the function.

Next we need to break our task into small subtasks. In our case, the task of printing out all the letters of a string is already simple, but the magic of recursion is that even the simplest task can be broken down into an even simpler subtask. What could it be like?

If we want to understand how to print all the letters of a string, then we only need to understand how to print the first letter of the string. That's all! To do this, we take the first letter of the string and print it:

first_letter = text[0]

print(first_letter)

And then we turn on the magic of recursion: we return our same function, but without the first letter, because we solved the problem: recurs_print(text[1:])

Problem 2

To deepen our understanding of recursion, let's try to solve a slightly more complex problem. But its solution will be in many ways similar to the solution to the previous problem. Task: return even numbers from a list.

First, let's define the base case. It is the same as in the previous task: if the list is empty, quit.

Now let's break our problem into sub-problems. Again, this is very similar to the letter printing task. To check all the numbers in a list, you just need to check the first number. To do this we write:

first_element = num_list[0]

if first_element % 2 == 0:

result.append(first_element)

Please note that in this case we are passing result as a parameter to the function. If we did this inside a function, then assigning the empty list to the name result would be repeated every time the function was called. Thus, we would end up with an empty list. But if we use result as a parameter, then its value will not be recalculated on each call.

And at the end we use the magic of recursion again: the function calls itself, but without the first element for which we checked the condition above.

Problem 3

At this stage, the question might arise: why solve simple problems in a more sophisticated way? And the following problem will help us answer this question. A huge amount of open data is stored on the Internet in json format. Roughly speaking, this is a “Python” dictionary in which there are keys and values. These dictionaries, as a rule, have nested dictionaries and lists, which in turn can also contain nested dictionaries. And often there is a need to find some value in such a complex data structure. And due to the fact that a rare service on the Internet (especially a government service) provides data in its pure form, you have to write cumbersome code with many conditions and exceptions for an essentially very simple task - searching for a value by key.

And using recursion, we can write a function that will allow us to look up a value in a dictionary with any number of nested dictionaries. (This function will not work if there is a list in the dictionary - we did this deliberately, because this part of the code was completed by participants in our Telegram chat as part of a competition).

So, let's first define the base case. It's simple: if the key is in the dictionary, return its value: if key in obj: return obj[key]

Otherwise, we need to use a for loop to iterate through all the keys and values ​​of the dictionary to see if there are nested dictionaries among the values. And if the object is a nested dictionary, then we use the magic of recursion: we call our own function and pass it the object as a parameter.

The next line of code ( if result is not None ) is important because when our function tests the base case and does not immediately find a value for the key, it returns None . To prevent this from happening, we need to “order” it to return the value if it is None .

And we can test the operation of our function using the example of a reduced download of a government contract from the “Government Procurement” service. For example, we want to print the value of the key date, which is in a nested dictionary. To do this, we just need to write one line of code: recurs_find_key('date', data)

Support those
who is telling the truth! You can become our donor by making a one-time or monthly donation. We want to depend only on you - those who want to know the truth, those who are not afraid to be free. Help us tell you the Stories That Matter.Support Important Stories