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.