What is Recursion?!

4 min readJul 5, 2021

Let’s come and go deeper ;)

Recursion occurs when a thing is defined in terms of itself or of its type. In computer science is very famous to solve a problem calling itself several times until a stop condition.

So before study an example, let’s review some concepts:

What is a recursion?

Like we said before, recursion means call itself.

As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances

Infinite recursion

If a recursion never reaches a base case, it goes on making recursive calls forever, and the program never terminates. This is known as infinite recursion, and it is generally not a good idea. Here is a minimal program with an infinite recursion:

def recurse():
    recurse()

That’s why , we can say when we will do a recursion, we need the function that it calls itself and also a base case to stop it.

Why use recursion?

We can use a while or use recursion. Sometimes, it is easier to solve a problem using recursion when we will see that we need to call itself several times because with an interation, it will be more complex with index, etc.

Also it is important to say that in a iteration the stop conditional is inside of the while(here) but in recursion is in the base case. for example:

def recurse(x):# base case:   
    if (x == 4)
        return(1);
    recurse(x - 1)

How to use recursion?

A recursive function requires two parts like we said before:

a recursive call
base case.

The recursive call is the part of the function that will keep calling itself and the base case is the stop conditional. We will see better in the next example.

Let’s see an example below:

We can see that first, when the function starts, they go through admitted lines and when it comes to the return, the function call itself, with a parameter changed “y-1” until the stop conditional (if (y == 0) return(1)) is true. Let’s take an example and go deeper, when Xo = 7; Yo = 3, we can see in the heap:

Because Yo =3, It enters to the recursion in line 8, until (y ==0), that’s why, we can see the different values of y in the heap.

After it, because now the stop conditional is true, the recursion stop:

And now, it will start to do the operation to calculate the final return. Operation: we can see in the next image , that it multiplies itself x times when x is the number of times it is in the heap (in this case = 3 , because the goal is to have the 7 ^ 3)

In here we can se that the result will be x*x*x (y times)

So finally, we can have the final result (x*x*x = 7*7*7 = 343). We can see the result in the stack

Conclusion:

And that’s all!!! We can see that in this example of calculate a power of 7³ . It is easier to solve with a recursion than iteration. That’s why because we need to call itself several times to multiply itself.

I hope you enjoyed reading it as much as I did writing it.

See you,

Kate