Recursion in Java with Examples

Introduction A recursive method is one which calls itself. That sounds like a recipe for an endless loop, but used well, recursion solves problems which break naturally into smaller copies of themselves - factorials, folders within folders, tree structures, and many sorting and searching algorithms. This tutorial explains recursion in Java with examples. We will start with the two parts every recursive method needs - a base case and a recursive case. We will then trace how recursive calls work on the call stack. Next we will write several recursive methods, and see what happens when the base case is missing. Lastly, we will compare recursion with loops, and see how to avoid the hidden cost of naive recursion.

(Note - Recursion relies on how method calls use the call stack, which is explained in Java MethodsClick to read tutorial: Java Methods: Defining, Calling and Returning Values.) Base case and recursive case Every recursive method needs two parts -

Base case: the simplest input, which the method answers directly without calling itself. It is what stops the recursion.
Recursive case: for any other input, the method calls itself on a smaller version of the problem, and uses that answer to build its own.

Each recursive call must move closer to the base case. The classic example is the factorial: n! = n × (n - 1)!, with 0! = 1 as the base case.

A recursive factorial method

//Factorial.java
public class Factorial {
  static long factorial(int n) {
    if (n <= 1) {                     // base case
      return 1;
    }
    return n * factorial(n - 1);      // recursive case: a smaller problem
  }

  public static void main(String[] args) {
    for (int n = 0; n <= 5; n++) {
      System.out.println(n + "! = " + factorial(n));
    }
    System.out.println("20! = " + factorial(20));
  }
}

OUTPUT of the above code

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
20! = 2432902008176640000

How recursion works on the call stack Each call to factorial() gets its own stack frame with its own n. The calls go down until the base case is reached, and then the results come back up, each frame multiplying by its own n. Adding prints, indented by the depth of the call, makes this visible -

Tracing recursive calls

//TracedFactorial.java
public class TracedFactorial {
  static long factorial(int n, int depth) {
    String indent = "  ".repeat(depth);
    System.out.println(indent + "factorial(" + n + ") called");
    if (n <= 1) {
      System.out.println(indent + "base case: return 1");
      return 1;
    }
    long result = n * factorial(n - 1, depth + 1);
    System.out.println(indent + "factorial(" + n + ") returns " + result);
    return result;
  }

  public static void main(String[] args) {
    factorial(4, 0);
  }
}

OUTPUT of the above code

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      base case: return 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

Four frames were on the stack at the deepest point. factorial(4) could not finish until factorial(3) had returned, which needed factorial(2), and so on down to the base case.

More recursive examples Recursion fits any problem that can be described in terms of a smaller version of itself.

Recursive methods for sums, powers, strings and binary search

//RecursionExamples.java
public class RecursionExamples {
  static int sumDigits(int n) {                      // sum of digits of 4096 = 4 + 0 + 9 + 6
    if (n < 10) return n;
    return n % 10 + sumDigits(n / 10);
  }

  static long power(long base, int exp) {            // fast power: halves the exponent each time
    if (exp == 0) return 1;
    long half = power(base, exp / 2);
    return exp % 2 == 0 ? half * half : half * half * base;
  }

  static String reverse(String s) {                  // reverse = last char + reverse of the rest
    if (s.length() <= 1) return s;
    return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
  }

  static int binarySearch(int[] a, int target, int low, int high) {
    if (low > high) return -1;                       // base case: empty range, not found
    int mid = (low + high) / 2;
    if (a[mid] == target) return mid;                // base case: found
    return a[mid] < target
        ? binarySearch(a, target, mid + 1, high)     // search the right half
        : binarySearch(a, target, low, mid - 1);     // search the left half
  }

  public static void main(String[] args) {
    System.out.println("sumDigits(4096) = " + sumDigits(4096));
    System.out.println("power(2, 30)    = " + power(2, 30));
    System.out.println("reverse(\"Java\") = " + reverse("Java"));
    int[] sorted = {3, 8, 15, 21, 42, 57, 90};
    System.out.println("index of 42     = " + binarySearch(sorted, 42, 0, sorted.length - 1));
    System.out.println("index of 5      = " + binarySearch(sorted, 5, 0, sorted.length - 1));
  }
}

OUTPUT of the above code

sumDigits(4096) = 19
power(2, 30)    = 1073741824
reverse("Java") = avaJ
index of 42     = 4
index of 5      = -1

Explanation of the code

sumDigits() splits off the last digit with % 10, and recurses on the rest with / 10, until one digit is left.
power() uses base^exp = (base^exp/2)², so it needs only about 5 calls for an exponent of 30, instead of 30 multiplications.
binarySearch() has two base cases - found, and an empty range - and each call halves the range. Compare it with Arrays.binarySearch() from the Arrays class tutorialClick to read tutorial: Java Arrays Class: sort, binarySearch, fill, copyOf.

Missing the base case - StackOverflowError Every call adds a frame to the stack, and the stack has a limited size. If the base case is missing, or the recursive call does not move towards it, the calls never stop, and the JVM throws a StackOverflowError.

Recursion without a reachable base case

//NoBaseCase.java
public class NoBaseCase {
  static int depth = 0;

  static long countDown(int n) {
    depth++;
    if (n == 0) return 0;          // never reached when n starts odd and we step by 2
    return countDown(n - 2);
  }

  public static void main(String[] args) {
    try {
      countDown(7);
    } catch (StackOverflowError e) {
      System.out.println("StackOverflowError after about " + depth + " nested calls");
    }
  }
}

OUTPUT of the above code (the exact depth varies)

StackOverflowError after about 17730 nested calls

7, 5, 3, 1, -1, ... skips right over 0, so the base case is never reached. Always check that every input eventually reaches a base case - and remember that even correct recursion can overflow the stack for very deep inputs, such as summing a list of a million elements one at a time. Recursion vs loops, and the cost of naive recursion Anything written with recursion can also be written with a loop. Loops use no extra stack frames and are usually a little faster; recursion is often shorter and clearer for problems that are naturally recursive - trees, nested structures, divide-and-conquer algorithms such as merge sort and quick sort.

Recursion can also hide a large cost. The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, ...) are defined recursively, but a direct recursive method recalculates the same values again and again -

Naive recursion vs a loop for Fibonacci numbers

//Fibonacci.java
public class Fibonacci {
  static long calls = 0;

  static long fibRecursive(int n) {
    calls++;
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
  }

  static long fibLoop(int n) {
    long previous = 0, current = 1;
    if (n == 0) return 0;
    for (int i = 2; i <= n; i++) {
      long next = previous + current;
      previous = current;
      current = next;
    }
    return current;
  }

  public static void main(String[] args) {
    int n = 30;
    System.out.println("fibRecursive(30) = " + fibRecursive(n) + " using " + calls + " calls");
    System.out.println("fibLoop(30)      = " + fibLoop(n) + " using " + (n - 1) + " loop steps");
    System.out.println("fibLoop(90)      = " + fibLoop(90));
  }
}

OUTPUT of the above code

fibRecursive(30) = 832040 using 2692537 calls
fibLoop(30)      = 832040 using 29 loop steps
fibLoop(90)      = 2880067194370816120

The recursive version made over 2.6 million calls for n = 30, because each call branches into two, and the number of calls roughly doubles each time n grows by one. The loop needed 29 steps, and can calculate fibLoop(90) instantly. When a recursive method calls itself more than once with overlapping inputs, store results which have already been calculated (memoization), or use a loop. Summary In this tutorial we first saw that every recursive method needs a base case, which stops the recursion, and a recursive case, which calls the method on a smaller problem. We then traced a recursive factorial through the call stack. Next we wrote recursive methods for summing digits, fast powers, reversing a string and binary search. We then saw that a missing or unreachable base case causes a StackOverflowError. Lastly, we compared recursion with loops, and saw how naive recursive Fibonacci makes over 2.6 million calls where a loop needs 29 steps. In the next tutorial, we will look at the difference between static and instance methods.

Java Fundamentals Tutorials
Java Varargs: Variable-Length Arguments with Examples Static vs Instance Methods in Java Java Methods: Defining, Calling and Returning Values Is Java Pass-by-Value or Pass-by-Reference? Method Overloading in Java with Examples What is Java? History, Features, Editions and Uses

Recursion in Java with Examples

Click on a category to view all articles