Hello, everyone! How are you?
Today we’ll talk a little about recursion.

Recursion has many definitions, but in computing it describes algorithms that are defined in terms of itself, which means that in it’s implementations it calls itself.

The concept might seem complicated for someone who has never heared of it, but it is something extremely useful, depending on the problem you have in hand.

On this post, I’ll use the classic examples of rescursive algorithms, but I’d like to make it clear that it can be used for much more practical things, as I’ll show you on the end of this post.

Even though recursion isn’t language specific, it is a very important part of functional programming, so if you’re entering that area ,or thinking of it, it’s something you should have on the tip of your fingers.

Well, let’s move to the first example, the calculation of a factorial number.

The easiest way to implement a recursive algorithm, is to think on the mathematical function that represents it, so let’s do that.

A factorial number is represented by an exclamation point (!) preceded by the number to be calculated, therefore, if we want to calculate the factorial of 5, we can represent it like this: 5!

The calculation is made by multiplying every whole number, since the informed value, all the way to the number 1, so in the case of 5, it would look like this:

And the function to calculate the factorial of a number n, would be like this:

Okay then, to calculate the factorial of n, we must calculate the factorial of n-1, meaning that to evaluate this function, it needs to execute itself internally, the fact that this seems repetitive indicates that we can apply recursion. So here’s a very simple implementation of this calculation in Java:

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

You see that the method calls itself up to a certain condition, that condition also comes from the definition of a factorial number. The explanation given by any math teacher, or at least the ones that I met, is that the factorial of 0 is 1 by definition, so we have a case where the function does not invoke itself, we call that a stopping condition.

Another example is the calculation of a term in the Fibonacci sequence, which is a succession of natural numbers, in which the 2 first terms are 0 and 1, and every subsequent term corresponds to the sum of it’s 2 predecessors, observe the image below:

Seeing this image, we can assume that the sequence follows this function:

As you probably noticed, once again the function is defined in terms of itself, so it is recursive, if we translate it to Java it would look like this:

public static int fibonacci(int n){
    if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else{
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Now as promised, I present a recursive code that I run daily.
At work I had to write a script for the deletion of directories, because a certain temporary directory was never deleted by some reason, in this case, I believe recursion was the best choice I could have made, and with a simple Scala script the problem was solved, here’s the function:

def deleteFiles(file: File): Boolean = {
    if (file isDirectory) {
        for(f <- file.listFiles){
            deleteFiles(f)
        }
    }
    file.delete
}

Now recursive functions may have a problem, like in the factorial function. In Java, if you try to calculate the factorial of a very large number using the algorithm presented here, you could run into a StackOverflowError. Why is that? How can I avoid it?

That subject will be approached on my next post, also about recursion

I hope you enjoyed it! See you next time!