Recursion

Programming languages allow the usage of certain mechanisms to simplify solving a problem. Recursion is one of those mechanisms. It is the ability of a method to call itself. When properly designed, a recursive method can simplify the way a solution to a certain problem is expressed using code.

Classic examples in recursion include the computation of the factorial of a number or the sorting of an array of numbers. For the sake of simplicity, we are going to look at the first case: finding the factorial of a number.

class Example11 {

    public static long fact ( int n ) {

        if ( n == 1 ) return 1;

        return n * fact ( n – 1 );

    }

    public static void main(String[] args) {

        int input = Integer.parseInt(args[0]);

        long factorial = fact ( input );

        System.out.println(factorial);

    }

}

To run this code, you will need to go to the terminal and call the example from there with java Example11 m, where m is the integer whose factorial will be calculated. Depending on where you created the project on your computer, it could look like this (note that we have shortened the path to the example to keep it clean):

usr@localhost:~/IdeaProjects/chapter03/[...]production/Example11$ java Example11 5

120

Or, it could look like this:

usr@localhost:~/IdeaProjects/chapter03/[...]production/Example11$ java Example11 3

6

The result of the call is the factorial: 120 is the factorial of 5, and 6 is the factorial of 3.

While it might not seem so intuitive at first sight, the fact method calls itself in the return line. Let's take a closer look at this:

public static long fact ( int n ) {

    if ( n == 1 ) return 1;

    return n * fact ( n – 1 );

}

There are a couple of conditions that you need to meet when designing a functional recursive method. Otherwise, the recursive method will not converge to anything:

1. There needs to be a base condition. This means you need something that will stop the recursion from happening. In the case of the fact method, the base condition is n being equal to 1:

   if ( n == 1 ) return 1;

2. There needs to be a way to computationally reach the base condition after a certain number of steps. In our case, every time we call fact, we do it with a parameter that is one unit smaller than the parameter of the current call to the method:

   return n * fact ( n – 1 );