What is recursion?

1. What is recursion?

Very good work on lambda expressions and their practical use. Now, let's dive into the most frequent topic in coding interviews: recursion!

2. Definition

Let's start with a definition: Recursion is the process of defining a problem in terms of itself. Or, more technically: Recursion is a process in which a function calls itself as a subroutine.

3. Example: Factorial $n!$

To understand recursion, we will use the example of factorial calculation. A factorial is a sequential multiplication of integers starting from the number itself down to 1. For example, let's consider n = 4. The above written expression will look like that. It's 4 multiplied by 3, then multiplied by 2 and one at the end. Therefore, the result is 24.

4. Factorial - Iterative Approach

Notice that a factorial can be re-written in the opposite direction: from 1 to n. This is the most common representation for an iterative algorithm to calculate a factorial. Let's choose 4 again and go through the algorithm. We initialize our temporary variable result to 1. Then, we get into the loop. The first iteration gives us 1 again. The second iteration gives us 2. Then, we get 6. And finally, we get 24. As we can see, the iterative approach does its job. However, there is a more elegant way to solve the problem.

5. Factorial - Recursive Approach

Notice that a factorial can also be written like this: the number itself multiplied by the factorial of a lesser number. We can write it as the following Python function. And this is a pure recursion: function calling itself! But what's wrong with that code? We dive into an infinite amount of calls! To change that we must have a stopping criterion or a so-called base case that will prevent infinite calling by defining a well-defined output for a given input. Let's recall that the multiplication sequence in the factorial ends with 1: no more further calls! Therefore, we can define the base case for the factorial function when n equals 1. Taking this into account, let's modify our function. Now, we can be sure that our factorial will be calculated correctly for all the numbers higher than 1.

6. Wrapping Up

Great! We recalled what recursion is. To wrap up, recursive functions consist of two main parts: A recursive call to a smaller problem of itself, and a base case that prevents infinite calling. Now, where can we encounter recursion in data science?

7. Example - Decision Trees

A good example of it is decision trees! Why? Let's recall that a decision tree is a model that is used to predict different outcomes depending on its logical structure. In the case of classification trees, the outcome is a category as depicted on the slide.

8. Traversing a Decision Tree

Given a new sample, how can we traverse the tree to find out its category? Right, we can use recursion! Let's create a pseudo algorithm for the given classification tree. First, let's define our function. It should return a category given a sample and a node of the tree. In the function body we check if the node has a splitting. If there is a splitting, we choose either left or right child node depending on the conditions met. And here is our recursion! Given a child node, we apply a recursive call to the same function! What should be done next? Right, a base case! We did not specify it. It should be defined if the node does not have a splitting afterward.

9. Traversing a Decision Tree

In other words, we have a leaf node that stores a category. Therefore, we can simply add the corresponding return statement to the end of our function. In this way, we defined our traversal function through recursion!

10. Let's practice!

Now you know what recursion is, and which examples can be found in data science. It's time to practice!

Create Your Free Account

By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.