Recursion

Recursion is a powerful principle that allows something to be defined in items of smaller instances of itself.

This article focuses on two important topics:

• The basics of recursion
• Tail recursion

The basics of recursion.

Before we start talking about the properties of recursion and how they are used in a certain programming language, we first need to know what is recursion? We can define recursion as followed:

Recursion is that property that has a function by which said function can call itself. From this premise we can conclude that we can use recursion as an alternative to iteration, (since iterating is repeating a process n number of times) and recursion (it would be calling the function n number of times)

Therefore, consider a problem that is not initially thought recursively: Make a program that calculates the factorial of a number, this number being positive where we also consider the number zero as positive.

The factorial of n, written n! is the product of all numbers from n dow to 1. For example:

4! = (4) * (3) * (2) * (1)

1. The iterative way: One way to calculate this is to loop through each number and mutiply it with the product of all preceding numbers, that is:

Figure 1.

n! = n * (n - 1) * (n - 2) * (n - 3) * ... * (1)             with n >= 0

Represent that expression in a programming language, in this case C, serial something like this:

#include <stdio.h>

int main(void)
{
    int Number = 4;
    int Result_Of_Factorial;

    Result_Of_Factorial = Number;

    while (--Number)
        Result_Of_Factorial *= Number;

    printf("%d\n", Result_Of_Factorial);
}

The output of the program would be: 24.

2. Another way to look at the problem is to define n! as the product of smaller factorials: look at figure 1 above.

Figura 2.

we know that n! = n * (n - 1) * (n - 2) * (n - 3) * ... (1)

we can conclude that  (n * 1)! = (n - 1) * (n - 2)!

This in turn would be (n - 2)! = (n - 2) * (n - 3)!

And so on recursively until reaching number 1.

This can be more formally defined as:

                    {  1                      if n = 0, n = 1.
             F(n) = { 
                    {  n * F(n -1)            if n > 1.

Having clear the two previous images, they allow to define the syntax of a function that calls itself in a language like C:

A function that has statements between which there is at least one that calls the function itself is said to be recursive, suppose we have the function FunctionA and FunctionB, a non-recursive program would be written as follows.

void FuncionA(...)
{
          ...
}

void FuncionB(...)
{
          FuncionA(...)      
}

With a recursion organization you have the following.

void FuncionA(...)
{
          ...

          FunctionA(...)

          ...
}

Note: In mathematics the definition of a function in terms of itself is called inductive and naturally leads to a recursive implementation, therefore, recursion in programming is very useful for solving mathematical problems and not only that, it is also found in algorithms of comparison and also applies. a lot in binary tree structures

In figure 2 we saw how this is represented mathematically, which can even be represented as a sum. they are just different ways to represent the same, now we move on to represent this in a programming language

#include <stdio.h>

int Fact(int Number)
{
    if (!Number || Number == 1)                            (1)

        return (1);

    else
        return (Number * Fact(Number - 1));                (2)
}

Note: Recall that !Number is equal to Number == 0.
  

Now we analyze the image above.

(1). As in iteration, in recursion there must be a statement that cancels the call to the function again, since if this does not happen then the function would be called infinitely as it would happen if we did not put a break condition in an iteration, this is equivalent to:

1.Iterative      

while (--Number)      # Recall that
                        while (--Number) is equal to while (Number != 0)
# This is our condition of break.

2. Recursive

if (!Number || Number == 0)

      return (-1);

# This is our condition of break, Since at that point the function stops calling itself, that is, for the calling process

(2). Where the concept of recursion applies, this is where we call the function again.

The property that has the function of calling itself, keeps with it some characteristics that are the following.

1. winding phase: In the winding phase each recursive call perpetuates the recursion by making an additional recursive call itself, the winding phase terminates when one of the calls reaches a terminating condition (break condition).
2. Once the winding phase is complete, the process enters the unwinding phase, in which previous instances of the function are revisited in reverse order, this phase continue until the original call returns.

Image taken from the book: Mastering Algorithms with C

You can see it in a much more graphic way in the following link

Note: First part finished, the second part talks a bit about how this affected the memory and the second blog topic will be explained.