Recursion in Programming

In today’s post we’ll discuss a very important topic in programming: recursion. It’s true that when you first study this concept, it can seem challenging, but it’s actually quite simple. It should be noted that it’s not just limited to the .Net environment, but applies to all programming languages.

1 - What is recursion in programming?

Recursion is a concept that refers to when a method calls itself. When creating a recursive method, you must make sure that it will finish; inside the method, you have to ensure that it doesn’t keep calling itself endlessly. This means the cycle is finite.

We must be very careful when making recursive calls, as uncontrolled use could overflow your computer’s memory and cause your program to crash.

2 - When to use recursion?

As can be seen from the previous description, we can use recursion to replace any kind of loop. Even so, it’s not used too often in the professional world, since an error can be catastrophic for memory, and having a list with millions of elements can use a lot of memory. Still, most of the time, we use recursion for search or sorting algorithms.

The base case is the condition that ends recursion.

Example 1

An example is calculating the factorial of a number.^{*Multiplying all the numbers between two integers. In mathematics, this is denoted as n! where n is the last number to check. You must start from 1.}

Example using an iterative method

public static int FactorialIterativo(int numero)
{
    int i, resultado = 1;
    for(i=1; i <= numero; i++)
    {
        resultado = resultado * i;
    }
    return resultado;
}

Example using a recursive method

public static int FactorialRecursivo(int numero)
{
    if (numero == 0) return 1;
    return numero * FactorialRecursivo(numero - 1);
}

3 - The recursion stack

A computer’s memory is divided into 4 segments

• Code segment: stores the program instructions in machine code.
• Data segment: stores static variables or constants.
• Heap: stores dynamic variables.
• Program stack: this part is used for local variables and the parameters of the function currently being executed.

When we call a function (or method), the process is as follows:

1. Space is reserved in the stack for the function’s parameters and its local variables.
2. The stack stores the address of the line of code from which the method was called.
3. The function’s parameters and their values are stored on the stack.
4. Finally, the memory assigned in the stack is freed when the function ends, and execution returns to the original code call.

On the other hand, when the function is recursive:

• Each call creates a new function call with its own local objects.
• It’s executed completely again, up to the self-call. It again creates new parameters and local variables in the stack for each recursive call made.
• Once finished, the memory on the stack is freed one by one, starting from the last function created up to the first, which is the last one to be released.