Recursion for understanding Recursion
I’ve always heard that terms or ideas can’t be explained by themselves. Well, here’s where recursion comes in and breaks it all. Recursion is a very useful tool for mathematics and programming: in both cases the recursion occurs when a function is defined by an implementation of itself.
A good example in maths is the formula to calculate the factorial of a non-negative integer: if it’s 0, the result is 1, but if it’s greater than 0 the result is the multiplication of the number by the factorial of the same number minus 1
Now I’ll try to explain you how recursion works in programming. Let’s get to this C function for instance:
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);
}
It takes two numbers, x
and y
, and raises x
to the power of y
. Suppose we want to calculate 2³, so x
is 2 and y
is 3. The first call to this function will create a space in the stack of the memory where the function executes. Because y
is not equal to 0 neither less than 0, the function will call itself but now x
stands in 2 and y
is 2. This new call creates another space in the stack where this call will execute. And it will work in the same way until y
will be equal to 0: in this point, the function will return 1 to the previous call and so on every call will return a new number until the first call. Here i attach you an animation to see more clearly how this recursive function (and many others) works on the stack.