Image for post
Image for post

To Understand Recursion, You Must First Understand Recursion

float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
printf("Current x, y: %f, %f\n", x, y); return (_pow_recursion(x, y - 1) * x);
}

Recursion can be a tricky concept to wrap your head around, but think of it as a stack of blocks that pop down to return it’s result. The program above will be our recursive example for learning recursion. Take note of the exit condition, which is if (y == 0) return 1; . This means that when y becomes 0, the program will exit and give you back the result of it’s recursion. The next piece of code to look at it is return (_pow_recursion(x, y - 1) * x); , this is how our program will recursively call itself until it hits it’s exit condition to pop down to give our result. A better visual will be drawn below:

int main(void)
{
int res = 0;
res = _pow_recursion(2, 5);
printf("Result = %d\n", res);
return (0);
}
Image for post
Image for post

We will use this input in our power recursive program, setting x = 2 and y = 5 , the picture below the code is how the stack looks like when it is computing the recursive program. Starting from the bottom, we see that it wants to return 2 * 2 , but it can’t do that until it knows what 5 - 1 is. So it adds to the stack after computing what 5 - 1 is, and it becomes 4 - 1 . This goes on until it hits it’s exit condition at the very top, which is if (y == 0) return (1); . At this point of the stack, it can finally compute it’s pending multiplies by going down the stack:

Image for post
Image for post

Now from the top of the stack, it exits and goes down to 2 * 2 which is 4. Now its holding 4 , but cannot return until it goes down because of a pending multiply. So it does 4 * 2 , and now it holds 8 , and so on until it hits the last of the stack where it returns what it is holding; which is 32 . Below is the the entire program that has been listed in this article:

Image for post
Image for post

In conclusion, if you think of recursion while being on a stack like how the images above are; it might be easier to understand the concept of how it works. Recursion builds a stack until it hits it’s exit condition, and then it pops the stack from top to the end (bottom) while holding onto it’s return value. Once it’s back down to the start of the stack, it returns it’s value and the program finishes.

Sources:

Software Engineer | Linux Love | Cat Love | https://github.com/kai-dg

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store