How works
What is recursion?
Recursion is a process by which a function calls itself repeatedly until some condition is satisfied. The process is used for repeated computations in which each action is determined by a previous result. Many iterative problems can be written in this way.
Two conditions must be satisfied for a problem to be solved recursively:
First: The problem must be written recursively.
Second: The problem statement must include an end condition.
Let’s explain recursion with the following program to find out the power of a number
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);
}
void main(void)
{
printf("%.f\n", _pow_recursion(5, 2));
}
First the function enters the main where it prints what the pow_recursion function returns in this case a floating number.
We enter the function pow_recursion where we assign the values (5, 2), where 5 is the base number and 2 is the exponent that is to say 5 * 5 = 25, in the stack we see it this way:
We check the conditions (y == 0) and (y < 0) in this case none is fulfilled.
We enter to the return where we call again to our function passing it the current parameters (5, 2–1) * 5) this means that we pass it (5, 1), because we only take the inside parenthesis not yet multiplied by five, we continue verifying that none condition is fulfilled and we call again our function, in the stack it would be seen this way
One of our conditions is fulfilled, so we return one to the function _pow_recursion, that is, we replace the value we have in the first parenthesis (the inside) by the value we return, and complete the operation, in this case is a multiplication by x, which has the value 5, that result returns again and replaces the parameters mentioned above, the new result returns to do the same process and so on until the beginning.
Sources
Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java
