Five examples of recursion in Java

Examples of recursion in Java

Recursion in Java gets a bad rap.

Experienced developers shun the practice over fears that an excessive number of recursive callbacks will trigger a StackOverflowError. However, many junior developers think recursive Java programs are easier to understand. They find recursive logic clearer than comparable solutions that use iterative loops.

Is recursion in Java a good approach to complex problem solving? I’ll share my thoughts on the topic at the end of the article. But first, explore these five Java recursion examples on your own and decide for yourself how much you like this programming approach.

5 recursive Java examples

We’ll use these following recursive Java examples to demonstrate this controversial programming construct:

1. Print a series of numbers with recursive Java methods
2. Sum a series of numbers with Java recursion
3. Calculate a factorial in Java with recursion
4. Print the Fibonacci series with Java and recursion
5. A recursive Java palindrome checker

A simple Java recursion example

A simple program is always the best place to start when you learn a new concept. This first Java recursion example simply prints out the digits from one to the selected number in reverse order.

package com.mcnz.recursion;
public class VerySimpleRecursionExample {

  public static void main(String[] args) {
    callMyself(9);
  }
  /* The recursive Java method */
  public static void callMyself(long i) {
    if (i < 0) {
      return;
    }
    System.out.print(i);
    i = i - 1;
    callMyself(i);
  }
}

This program simply passes the number 9 to the program’s callMyself method. This method prints the number, subtracts one from the number, and then calls itself again until the number zero is reached. The result? All of the numbers from the given number to 1 are printed out in reverse order.

Sum a series of numbers

In the previous example, the recursive Java method returned void. In this example, the recursive method returns a whole number that represents an ongoing sum.

The recursive Java logic is as follows. Start with a number and then add that number to one less than itself. Repeat that logic until you hit zero. Once zero is encountered, the total sum of all numbers from the starting number down to zero has been calculated.

package com.mcnz.recursion;

public class RecursiveSumOfAllNumbers {

  public static void main(String[] args) {
    long sumOfAllNumbers = sumOfAllNumbers(9);
    System.out.println(sumOfAllNumbers);
  }

  /* A recursive Java example to sum all natural numbers up to a given long. */
  public static long sumOfAllNumbers(long number) {
  /* Stop the recursive Java program at zero */
    if (number != 0) {
      return number + sumOfAllNumbers(number - 1);
    } else {
      return number;
    }
  }
}

Recursive Java factorial program

If we can calculate a sum of a series of whole numbers, it’s not that big of a stretch to multiply them together as well. That’s what the recursive Java factorial program does. It provides a total of a sequential series of numbers multiplied against each other.

Here is the logic for a Java factorial program that uses recursion:

package com.mcnz.recursion;

public class RecursiveJavaFactorialProgram {

  public static void main(String args[]) {
    long nFactoriral = factorialProgram(9);
    System.out.println(nFactoriral);
  }

  /* Java factorial program with recursion. */
  public static long factorialProgram(long n) {
    if (n <= 1) {
      return 1;
    } else {
      return n * factorialProgram(n - 1);
    }
  }
}

Recursive Fibonacci series

In this example, you’ll calculate the Fibonacci series in both iterative and recursive Java programs. This is actually the most common assignment young developers get when it comes to learning recursion. Here’s what it looks like when implemented in a purely recursive manner:

package com.mcnz.recursion;

public class RecursiveFibonnaciJavaProgram {

  public static void main (String args[]) {
    for(long i=1; i<=9; i++){ 
      System.out.print(fibonacci(i) +" "); 
    }
    System.out.println();
  }


  /* A recursive Fibonnaci sequence in Java program */
  public static long fibonacci(long number) {
    if (number == 1 || number == 2) {
      return 1;
    }
    return fibonacci(number - 1) + fibonacci(number - 2);
  }
}

Recursive Java palindrome program

All of the Java recursion examples so far have dealt with numbers. But this example, the recursive Java palindrome checker program, deals with strings. Namely, it’s to see if a string is spelled the exact same way when the letters in the word are reversed.

package com.mcnz.recursion;

public class JavaPalindromeCheckProgram {

  public static void main(String[] args) {
    boolean flag = palindromeCheck("sitonapanotis");
    System.out.println(flag);
    flag = palindromeCheck("nine");
    System.out.println(flag);
    flag = palindromeCheck("amanaplanacanalpanama");
    System.out.println(flag);

  }
  /* Recursive Java example to check for palindromes */
  public static boolean palindromeCheck(String s){
    if(s.length() == 0 || s.length() == 1) {
      return true;
    }
    if(s.charAt(0) == s.charAt(s.length()-1)) {
      return palindromeCheck(s.substring(1, s.length()-1));
    }
    return false;
  }
}

In this example of recursion in Java, we first check to see if the first and last letters of a String are the same. We then move one letter in from both the start and the end of the String and recursively perform the same String comparison. If all the checks return true, then our Java palindrome program returns true. If not, the palindrome checking program returns false.

Proceed with recursive caution

When students first learn to code, the concept of recursion often seems natural. But there are drawbacks.

When you profile a recursive program in a tool like Java Flight Recorder and then compare the wall-clock times with iterative methods using a tool like Java Mission Control, you realize that recursion is an expensive programming concept. Other programs optimize recursive operations, but Java does not. If your goal is to optimize Java performance, you may do well to avoid recursion.

Furthermore, when recursion gets out of hand, it can generate a large number of self-referencing JVM stack frames, which can eventually lead to a StackOverflowError which can’t be recovered from.

Until the day when an LTS release optimizes for this programming construct, it is best to view these Java recursion examples as educational tools. Stick with iterative constructs in the systems you plan to put into production.

The source code for these Java recursion examples is on GitHub.