Java Recursion

The two ingredients of recursion

Every correct recursive method needs two parts. The base case is the simplest situation, where the method returns an answer without calling itself again. The recursive case is where the method calls itself with a smaller or simpler input, moving one step closer to the base case.

• Base case: the stopping condition that ends the recursion.
• Recursive case: the method calls itself with a smaller input.
• Progress: each call must move toward the base case, or the recursion never stops.

Example: summing numbers

To add up the numbers from 1 to n, notice that the sum of 1..n equals n plus the sum of 1..(n-1). The smallest case is when n is 0, where the sum is simply 0. That gives us a natural base case and recursive case.

public class Main {
  static int sumTo(int n) {
    if (n == 0) {          // base case
      return 0;
    }
    return n + sumTo(n - 1); // recursive case
  }

  public static void main(String[] args) {
    System.out.println(sumTo(5)); // 5+4+3+2+1+0 = 15
  }
}

// Output:
// 15

Here is how the calls unfold: sumTo(5) waits for sumTo(4), which waits for sumTo(3), and so on down to sumTo(0), which returns 0. Then the results are added back up as each call returns: 0, then 1, then 3, then 6, then 10, and finally 15.

Example: factorial

public class Main {
  static int factorial(int n) {
    if (n <= 1) {              // base case: 0! and 1! are 1
      return 1;
    }
    return n * factorial(n - 1); // recursive case
  }

  public static void main(String[] args) {
    System.out.println(factorial(5)); // 5*4*3*2*1 = 120
  }
}

// Output:
// 120

Recursion versus loops

Anything you can do with recursion you can also do with a loop, and vice versa. Loops often use less memory because they do not stack up pending calls. Recursion tends to shine for problems that are naturally self-similar, such as walking a tree of folders or the Fibonacci sequence.