Introduction to recursion

1. Introduction to recursion

We will now learn what recursion means and how we could use it for many problems.

2. What is recursion?

The first question we want to answer is what recursion is in general. As we can see in the picture, it is something that is always repeated. Accordingly, recursion is the use of a procedure, subroutine, function or algorithm that calls itself one or more times until a specific condition is met. Therefore, a recursion could simplify a complex problem by sharing the problem in smaller problems performed repeatedly. One really important fact about recursion is that we need a termination condition. Without one, the call of the small problems repeats indefinitely, as we can see in the picture.

3. Real-world example for recursion

Let's look at an example with a family tree. Everyone has a father and their father has a father. We can use recursion to find all fathers for the last five generations. To do this, we have to reduce the problem to smaller problems of the same type. The whole problem is to find all five generations and the small problem is to find the first father. So we find the first father, first, and in the second step, find the father of the father, until the termination condition of five is reached.

4. Facts about recursion

So that's how recursion works in general, but lets summarize some of the advantages and disadvantages. There are several advantages: the first obvious one is we can solve problems recursively if the problem can be reduced to the smaller problems of the same type. A recursively solved problem is easy to read and follow and a termination condition could be used to limit the number of iterations. Thinking of disadvantages, the execution time could be slower because the recursion function is called many times.

5. Recursion example - Sum of numbers

Let's try out a recursion problem. The problem we want to solve is to calculate the sum of consecutive numbers. It can be defined as shown on the slide. The number is 1 for the first iteration and for each following iteration the current number and the sum of the previous iteration is added. As an example, the result of five is 15. It is the sum of one plus two plus three plus four plus five.

6. Recursion example - Sum of numbers

Now, we are going to solve this problem with SQL and CTEs (Common Table Expressions). The initial query initializes the field for iteration and the SumOfNumber with one. In the recursive part, the current iteration number is added with the sum of the previous iteration. We can see that the termination condition is set to six. This means this query calculates the sum of numbers until it reaches six. Finally, the CTE is selected to get the wanted result.

7. Let's practice!

Now 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.