recursion

The Basics

Recursion is when a method calls itself in a program, with methods which do so being called recursive. This can be used to simplify many processes but must be done carefully as increases in complexity may lead to infinite loops where the program never stops calling itself.

Every recursive method needs a base case, which is the case in which the method stops calling itself. Aside from the base case, the recursive method needs to call itself to move towards the base case. This can be useful since many algorithms repeatedly implement steps, and recursion simplifies the code, alongside making it easier to read and maintain. It is worth noting that most recursive methods can be rewritten non-recursively.

Here is an example of using recursion to find the factorial of a number x:

          
    int factorial(int x) {

      if(x <= 1) return 1; // the base case
      else return x * factorial(x - 1); // the method calls itself to advance towards the base case

    }
      

Call Stacks

The Java Virtual Machine (JVM) keeps track of the methods being run using a call stack. Methods which enter the stack last will exit the stack first, but the methods are only allowed to exit the stack once recursion has ended, meaning the base case has eventually been met. If an infinite loop occurs, the stack will eventually run out of space and a stack overflow error will occur.

Tips

When working with recursion, it is important to carefully check and test the method and base case to make sure that the base case is always attainable. It's also important to make sure to include a base case and to make sure that such is correct for the function of the method. If recursion proves to make the problem even more complicated, the method can always be re-written non-recursively.