What are and how to use recursive functions

Recursion is a concept in programming in which a function calls itself to solve a problem.

Recursion is always something problematic and difficult to understand. Especially for those who are just starting out in programming.

However, some problems are easier to solve by applying recursion. Not all, by any means. More of a small part of the problems.

Operation of Recursion

In reality, recursion is easy to implement. We simply have a function that, at some point, invokes itself.

In reality, this structure is quite similar to a loop, in that it is a fragment of code that is executed several times.

However, it is not exactly the same. Each function call generates its own frame, where local variables are stored.

On the other hand, just as in a loop we have the risk of having an infinite loop, a recursive function can fall into an endless loop.

That is, when does this series of calls stop? At some point, the function has to do “something” other than calling itself. We will call these cases the base case.

As the base case is reached and the subproblems are solved, the recursive calls return, releasing the stack frames and allowing the original function to complete its task.

How to detect recursive solutions

How can we detect solutions that might be easier to solve with a recursive approach?

When we have a problem that involves multiple steps, and the result of executing each step returns a problem that is similar to the previous one.

For example, let’s say we have a tray with 5 cakes and 5 guests. We need to give one cake to each guest.

We take the first cake and do whatever needs to be done. We decide if one guest is hungrier than another, if they are intolerant to something, if they prefer chocolate or cream. It doesn’t matter, the point is we assign a cake.

Now we have one cake assigned, and the remaining problem is the same. But now we have 4 cakes and 4 guests left. This is a very silly example, but it serves to explain recursion.

At each step, the new problem remaining is identical to the previous one, but with fewer elements. This indicates that a recursive approach could be simpler.

Examples of recursive functions in different languages

Let’s see examples of recursive functions in different languages. To do this, we will use a very simple example, the calculation of the factorial of a number.

It is not the most interesting case in the world, nor the most practical. But it is very good because it is very simple.

We can identify that it is a problem susceptible to being solved by a recursive approach because, at each step, “what we have left to calculate” is identical to “what we have already calculated”.

That is,

And so on until we reach 1.

Let’s see how we would solve this problem recursively in different languages.

#include <iostream>

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    int resultado = factorial(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

using System;

public class Program {
    public static int Factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * Factorial(n - 1);
        }
    }

    public static void Main() {
        int num = 5;
        int resultado = Factorial(num);
        Console.WriteLine("El factorial de " + num + " es: " + resultado);
    }
}

function factorial(n) {
    if (n === 0 || n === 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

let num = 5;
let resultado = factorial(num);
console.log(`El factorial de ${num} es: ${resultado}`);

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

num = 5
resultado = factorial(num)
print(f"El factorial de {num} es: {resultado}")

Stack overflow and base cases

We have said that one of the problems of recursive functions is knowing when to stop. This is what we call the base cases.

If we do not stop the recursive calls, we get into an infinite loop. Each recursive call adds a stack frame to memory, and if these stack frames accumulate without being released, a stack overflow occurs.

Stack overflow occurs when a recursive function calls itself too many times, and the size of the call stack exceeds the established limit.

Let’s see an example that would generate a Stack Overflow.

int funcionRecursivaConStackOverflow(int n) {
    return funcionRecursivaConStackOverflow(n + 1);
}

int main() {
    int num = 0;
    int resultado = funcionRecursivaConStackOverflow(num);
    std::cout << "Resultado: " << resultado << std::endl;
    return 0;
}

In the previous example, the funcionRecursivaConStackOverflow function calls itself without a base case, which will cause a stack overflow and an abrupt closure of the program.

Therefore, we need one or more base cases that stop the process of recursive calls.

int funcionRecursivaConStackOverflow(int n) {
    return funcionRecursivaConStackOverflow(n + 1); 
}

int main() {
    int num = 0;
    int resultado = funcionRecursivaConStackOverflow(num);
    std::cout << "Resultado: " << resultado << std::endl;
    return 0;
}

In this case, we have added a conditional that stops the recursive calls. If n > 10, the recursive call is not made.

In the example, the result of the entire series of calls would be to show 10 on the screen. We have just made a counter up to 10 unnecessarily complicated. But for the example, it works 😉

The important thing is to understand that a recursive function has to have some kind of condition in which it does not call itself. Otherwise, you will have an endless loop and a stack overflow.

Logical equivalence of recursion - iteration

Any recursive function can be converted into a non-recursive function using an iterative approach. This often improves performance and avoids the risk of stack overflow.

For example, the calculation of the factorial in its recursive version

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

int main() {
    int num = 5;
    int resultado = factorial(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

Can be changed to an iterative version, for example as follows,

int factorialNoRecursivo(int n) {
    int resultado = 1;
    for (int i = 1; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

int main() {
    int num = 5;
    int resultado = factorialNoRecursivo(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

In this example, we have replaced the recursive function of calculating the factorial with a non-recursive version that uses a for loop to calculate the result iteratively.

Advantages and disadvantages of recursion

Advantages of recursion

• Ease: In certain specific cases, implementing a recursive solution can be simpler than an iterative solution

• Problem Division: Recursion allows us to divide a complex problem into simpler subproblems and solve each subproblem recursively.

• Efficiency for Hierarchical Structures: In problems involving hierarchical structures such as trees or graphs, recursion can be a natural and efficient way to traverse and manipulate these elements.

Disadvantages of recursion

• Complex Logic: Some problems may have complex recursive solutions, which can make their implementation and understanding difficult for less experienced programmers.

• Increased memory consumption: Each recursive call creates a new stack frame, which can lead to stack overflow if the number of recursive calls is very large. This can make recursive solutions less memory-efficient compared to iterative approaches.

• Lower efficiency: In some cases, recursive solutions may require more execution time compared to iterative approaches.

• Difficulty in debugging: Recursion can make debugging and error tracking difficult, especially when there are multiple recursive calls and the recursion depth is high.