Explaining Recursion

RECURSION DEFINITION:

A recursive function is a function that calls itself.

Yep, that’s it. No, I’m not initially misleading you this time. I promised conciseness, didn’t I?

Example:

To put the ideas into practice we will solve a simple exercise where we are creating a function to replicate the operation exponentiation using recursion in C language and analyze how the information is stored in the memory stack following the next code.

In this case, our function receives two parameters, x will represent the base and y the power. As you may know, the first condition of our program is defined by the exponentiation’s property of any number at 0 power will be equal to 1, it will also work as our termination condition. The second and third parameter of the equation will call itself I using the recursion concept we just previously mentioned, they will operate differently depending on if we introduce a positive or negative power, if y is positive it will call it self multiplying the x but reducing the power by 1, and repeat this process until reach the condition y = 0, a mathematically way to look it will be like this.

Using the example showing before is an easy way to understand recursion, but we want a closer approach to how actually the machine will interact with its data, and we will do so using the stack memory diagram.

The previous diagram shows how the function (_pow_recursion) stacks together in the memory execution. First, we will declare our variables in the main as we see it will be exported to the function without any modification, now when we enter to the function is where the magic happens, it will continually create new functions in the stack until the condition of y = 0 become truth and then they will be executed in descending order, and the result would be similar to the one we show in the mathematical diagram. Now we understand the concept and how to apply it there are some considerations when you are using recursion, those presented are probably the most relevant of all.

Avoid endless loops

Another problem to avoid when writing recursive functions is circularity. Circularity occurs when you reach a point in your recursion where the arguments to the function are the same as with a previous function call in the stack. If this happens you will never reach your base case, and the recursion will continue forever, or until your computer crashes, whichever comes first.