Katherine Soto

Jul 5, 2021

4 min read

What is Recursion?!

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?

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

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?

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 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:

functions that’s use recursion

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:

example of the recursion

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.

heap until the stop cnditional is true

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:

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

See you,

Kate