Java Recursion

Java Recursion

Recursion is the technique of making a function call itself. This technique provides a way to break down complicated problems into simple problems which are easier to solve.

Recursion can be a bit tricky to understand. The best way to figure out how it works is to experiment with it.

Recursion Example: Factorial

A classic example of recursion is calculating the factorial of a number. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.

For example, 10! (10 factorial) is 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We can write this with recursion. The key insight is that 10! is the same as 10 * 9!, and 9! is 9 * 8!, and so on.

The recursive function would look like this:

public class Main {
  public static void main(String[] args) {
    int result = factorial(5);
    System.out.println("Factorial of 5 is: " + result);
  }

  public static int factorial(int k) {
    if (k > 0) {
      // Recursive call
      return k * factorial(k - 1);
    } else {
      // Base case
      return 1;
    }
  }
}

Example Explained

When the factorial() function is called with a positive integer, it will recursively call itself by decreasing the number by 1. This continues until the number is 0. When the number is 0, the function just returns 1.

Let's trace factorial(3):

1. factorial(3) returns 3 * factorial(2)
2. factorial(2) returns 2 * factorial(1)
3. factorial(1) returns 1 * factorial(0)
4. factorial(0) returns 1 (this is the base case)

Now the results are returned back up the call stack:

• The result of factorial(0) (which is 1) is returned to factorial(1).
• factorial(1) finishes, returning 1 * 1 = 1.
• The result of factorial(1) (which is 1) is returned to factorial(2).
• factorial(2) finishes, returning 2 * 1 = 2.
• The result of factorial(2) (which is 2) is returned to factorial(3).
• factorial(3) finishes, returning 3 * 2 = 6.

The Halting Condition (Base Case)

Just as loops can run into the problem of infinite looping, recursive functions can run into the problem of infinite recursion. Infinite recursion is when the function never stops calling itself.

Every recursive function should have a halting condition (also known as a base case), which is the condition where the function stops calling itself. In the previous example, the base case is when the parameter k is 0.

Without a base case, the program would continue to call factorial() with negative numbers, leading to a StackOverflowError.