Recursion Blog

What is Recursion?

A quick google search will reveal that recursion is “the repeated application of a recursive procedure or definition.”. So what does that actually mean? Well, when we are talking about recursion sometimes a picture/video might help you understand. Below is an image that describes recursion it is a simple but helpful image.

So what exactly do we see happening in this image? Above we see the word recursion and a box around it. Then it continuously is going inward inside the boxes until it is not even visible anymore. In this case, recursion is calling the same image over and over again and it will keep going past what you can see in the image if it was able to.

Let's look at an example of recursion in code. Below is going to be a snippet of code that we can go through step by step and talk about.

So the first line has our function name _pow_recursion(x, y). Whenever this is called the function will start from the top and go through until returned. Lets go ahead and say we were given x = 2 and y = 2. When we take a look we can see there is an if statement to check if y is zero and if that is the case the function will end. Right now we have y as 2 so the first if statement would be passed and we would go on to check if y is less than 0 which it is not. We finally reach the final if statement which is to return the function with (x, y-1) * x); which would come out to 2 * 2 which would be 4. next we now have 2, 1 so we would go through the same steps as above and get 2 as a return value. Finally, now that we have 2,0 we would go to the first if statement and get a set return value of 1. Now that we have finished the recursion we would get the return in this order. 1, 2, 4. We will talk more about why that is below.

Now that the basics of recursion are understood how does recursion work with the Stack?

As seen in the picture above recursion is a Last in First out meaning that the last thing you do in the recursion will happen first. It is like building with legos if you build a tower of 2x2 lego bricks you then would start with the last block you put on when taking it apart.

Some cool videos to check out are below!