What is recursion

Article by: Codenga 08.06.2022

What is recursion

To understand recursion you must first become familiar with recursion. It's the kind of joke that's been circulating for years and scares novice programmers.

Recursion is just a specific approach to solving programming problems. This technique basically involves using a function that calls itself. But what's the point of all this? We'll talk a little bit about that in a moment.

Two main concepts

Many common problems can be solved in two basic ways.

Iteratively - using a loop
Recursively - using a function that calls itself.

Each of these ways has its pros and cons. It's best if we get straight to the examples.

Problem - iterative solution

Let's start by defining the problem. We have an array of integers: 1, 5, 1, 2. We want to sum these numbers. We will first try to use a loop. This appears to be, at first glance, the most natural approach to such a problem.

Here is the code for our solution:

					
def sum_iter(digits):
    result = 0
    for digit in digits:
        result += digit
    return result

print(sum_iter([1, 5, 1, 2]))

We use the Python language because it has a simple, clear syntax that is perfect for illustrating our problem.

We have a simple function sum_iter(). It takes a list of digits with numbers we want to sum, as parameters. With the help of the loop, at each iteration we add another number from the list to the result variable. Thanks to that, on the output we get the output sum of numbers.

This is an iterative solution. It means that it is based on a loop. The loop runs until all the numbers are added up.

Problem - recursive solution

We will try to solve the same problem recursively. Take a look at the code:

					
def sum_rec(digits):
    if len(digits) > 0:
        last_element = digits[-1]
        digits.pop()
        return sum_rec(digits) + last_element
    else:
        return 0

print(sum_rec([1, 5, 1, 2]))

A little more code than with the iterative solution. So let's focus on the key elements.

We have a functionsum_rec() that takes an array of numbers as a parameter.
Using the if statement, we check if the length of the array is greater than 0.
We assign the last element from the array to thelast_element variable.
Using thepop() method we remove the last element from the array
And finally the most important part. We return thesum_rec(digits) function call. So, we can say that thesum_rec() function calls itself.

Let's be clear. In this example above, the recursive approach is complicated - it's certainly less transparent than the iterative solution. So what's the point of it all?

Recursion at its core

How can the problem of summing numbers from an array be simplified? We actually have two problems here:

adding up consecutive numbers
detecting the moment when all numbers are already added up.

Problem one is solved using the operations we just mentioned. We call the function sum_rec(digits) and add the last element from the list (variable last_element). Only that such code will be executed infinitely if we don't stop it at the right moment.

That's why we have a conditional statement inside the function. It checks if there are any more values in the array: if len(digits) > 0. If yes, then we can continue calling the function. And if not, we have to abort with return 0.

And that's the whole idea of a recursive approach to problem solving.

Disadvantages, advantages, usage

In these examples above, it was clear that the traditional approach using loops is simpler, clearer, and friendlier. So why do we need all this recursion?

There are languages that do not typically have loops. Such languages sometimes condemn us to a recursive approach. This is admittedly a niche case but it can happen.
Recursive algorithms are sometimes easier to visualize and break down into simpler components. However, this depends on the nature of the problem you are dealing with
There are situations where a recursive approach will be more efficient. In practice, however, it requires experience and a good understanding of the intricacies of the problem you are dealing with.

Recursion is a fairly specific approach. Proper use of recursion usually requires experience and good judgment.