Recursion and you
Recursion is a tricky subject to new programmers. It is a concept I struggled to understand during my introduction to the programming world. As a mathematician friend explained to me, its similar to that of a “dream within a dream”. Here we are going to look at a recursive function, and try to explain it, conceptually and technically.
float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);
}To understand recursion, we must understand what a stack is. A stack is a data structure that holds data with a FILO (first in, last out) principle. In lay man terms, it means you can only interact with the topmost object. Adding to the top of the stack is called pushing, and removing from the top of the stack is called popping.
Functions use what is called a “call stack”. Whenever a function is called, that call is pushed to the call stack, and its return is when that call is popped off of the stack.
Recursion may seem like something advanced and intimidating at first, but it really isn't. Recursive functions are essentially functions that call themselves, which means that within a function call, there is a call to the same function. Albeit, they are pushed to the stack individually and are not part of the same call stack object.
Now lets go through our code.
We have a “power of” function that takes 2 float arguments and returns a float. Let’s ignore the first two if statements and focus on the return line.
return (_pow_recursion(x, y - 1) * x);This is where all the “recursive magic” happens. Let’s say we use 3 for x and 5 for y. So we want to find 3 to the power of 5. We run our code, and we will have our arguments 3, and 5 stored respectively as x and y. We will skip the first two if statements as y is neither 0 nor less than 0. Our code enters the return line, where we “return” into our first recursive call. This first call of our function was the first in the call stack, now our first recursive call is pushed to our call stack. Now the only difference here, is that we are subtracting 1 from y. Y is working as our counter for how many times to repeat the multiplication, and X is just our number. So we go into this call with x as 3, and y as 4. We ignore both if statements again and enter our 2nd recursive call. Now we have 3 calls on the stack, x as 3, y as 3. Repeat, 4 calls on the stack, x as 3, y as 2. Repeat, 5 calls on the stack, x as 3, y as 1. This is as far as we need the recursion to go in order to have this function provide the desired result, but recursion knows no bounds. The two if statements in this function are here designed to address exactly that. The famous stack overflow.
If we were to allow the recursion to run without any of the if statements, our y would eventually hit 0, then -1, then -2, and so forth. That isn’t what we want. This could go on forever, but it won’t, because we will eventually trigger what is known as a stack overflow. It is caused when a recursive function gets out of control (infinite loop) and doesn’t stop recursing. The if statements are what are known as a “base case”. The return line is what is known as a “recursive case”. Without these, our recursive function will never stop, and our recursive function won’t really be doing much recursion.
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);The first if statement is our base case. This is what will finalize the recursion. The 2nd if statement deals with negative powers.
return (_pow_recursion(x, y - 1) * x)Back to our recursive statement. The following image shows a conceptual drawing of how the call stack works as this code is ran. We can see how the call stack fills up, reaches the base case, then returns back until we have our desired result.
return (_pow_recursion(x, y - 1) * x)/* looks like below as it goes down the stack */return (1 * 3)
return (3 * 3)
return (9 * 3)
return (27 * 3)
return (81 * 3)
Hope this clears up recursion!
