From 0 to Senior in Python: Recursive functions under the hood

Recursive functions belong to the more complex concepts. Especially beginners struggle to understand them. I thought that I understand them. But I was wrong. But being wrong comes with the great opportunity to learn something.

Photo by Shamin Haky on Unsplash

What is a recursive function?

In short: A recursive function is a function that calls itself again from the inside of a function. It works like a loop and repeats calling itself until we reach a base case.

I thought for a while that this is enough to understand it. But I came to realise that I misunderstood how recursive functions really work or meant to work.😞

But recursive si a concept that can be very confusing. So, let’s make sure that you don’t fall into the same trap as I did.✌️

Imagine you’re standing in a line, waiting to enter a place and you want to know how many people are in front of you without leaving your spot. What could you do. You could ask the person in front of you, how many people are in front of that person. Since that person doesn’t know that either, it is going to ask the next person in line. That would go on until the question reaches the first person in line. This person could anser with to the second person in line. The second person could report this sum plus one to the third person in line and so on. At some point the final answer would reach you. Most likely this wouldn’t work in reality. But this is exactly how a recursive function works! It does something until it reaches a specific base case. In this example that would be the very first person in line. And then it goes all the way back and adds the result upp. 💁‍♂️

Recursive function 1: sum all non negative values of a given value

So, let’s try now to create a recursive function in Python. But instead of asking for the amount of people in the line, we sum all the non negative numbers from 1 to a given number.

Before we jump right in coding, let’s write down as a simple math term, want we want to do:

sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15
sum(7) = 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

Find the base case

So, the first step to approach this problem is look for the easiest input we can have for this problem. That would be 0.

sum(0) = 0

We can call this now our base case.

def get_the_sum(n):   
    # base case
    if n< 1:
        return 0
    
print(get_the_sum(0)); # Expected Output: 0

Find a pattern

In order to understand what we need to write we need to undestand how the different values interact.

sum(1) = 0 + 1 = 1
sum(2) = 0 + 1 + 2 = 3
sum(3) = 0 + 1 + 2 + 3 = 6
sum(4) = 0 + 1 + 2 + 3 + 4 = 10
sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15

So, as we can see, there is a pattern. From sum(1) to sum(2) we need one more step. sum(3) needs also one more step than sum(2) etc. That also means, that obviously sum(5) is the solution of sum(4) plus 5. And the solution to sum(4) is the sum(3)-case and 4 added to it.

So that means in a simple math term:
sum(2) = sum(1) + 2
sum(3) = sum(2) + 3
sum(4) = sum(3) + 4
sum(5) = sum(4) + 5

That also means:
sum(4) = sum(5 -1)
sum(3) = sum(4- 1)

So obviously we can generalise our problem:
sum(n) = sum(n -1) + n

Let’s try to implement that in our code.

def get_the_sum(n):    
    # base case
    if n < 1:
        return 0
    
    return n + get_the_sum(n - 1);
    
print(get_the_sum(1)); # Expected Output: 1
print(get_the_sum(2)); # Expected Output: 3
print(get_the_sum(3)); # Expected Output: 6
print(get_the_sum(4)); # Expected Output: 10
print(get_the_sum(5)); # Expected Output: 15

With the approach to find a base case first, then look at the pattern and generalise it, the code wrote itself more or less.

To make the process even clearer for you, let’s take a look at what happens when we call the function get_the_sum().

Let’s say we call it with 3.
The function starts and since the value is greater than 1, we hit a recursive case: 3 + return_the_sum(3 -1)
Now the function calls itself again and again hits a recursive case: 2 + get_the_sum(2 -1)
And of course the same thing happens the next case.
Finally the function reaches the case, when n not longer greater than 1. It returns 0.
Now the functions returns all the values back to itself, back to the case sum(3) and we end up with the result 6.

So, as you can see, the recursive function is actually not that hard, once you understood what really happens.

If you learned something from this article, leave me clap, a comment or share this article to support me. I welcome you to follow me here or on LinkedIn.

Happy coding.