Java Recursion

Java Recursion

Recursion involves a function invoking itself, offering a method to decompose intricate problems into more manageable ones for resolution.

.Understanding recursion can be challenging, but experimentation is the most effective approach to grasp its workings.

Recursion Example

While adding two numbers is straightforward, calculating the sum of a range of numbers is more intricate. In the given example, recursion is employed to add a range of numbers by simplifying the task into the addition of two numbers at a time.

Example

Use recursion to add all of the numbers up to 10.

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Example Explained

Upon calling the sum( ) function, it adds the parameter k to the sum of all numbers less than k and then returns the computed result. When k reaches 0, the function simply returns 0. During execution, the program proceeds as follows:

As the function does not recursively call itself when k equals 0, the program halts at that point and returns the final result.

Halting Condition

Similar to loops encountering the issue of infinite looping, recursive functions can face the challenge of infinite recursion, where the function continuously calls itself without termination. It’s crucial for every recursive function to incorporate a halting condition, which denotes when the function ceases to call itself. In the earlier example, the halting condition occurs when the parameter k reaches 0.

Examining various examples aids in comprehending the concept more effectively. In this instance, the function sums a range of numbers from a starting point to an ending point. The halting condition for this recursive function is when the end value is not greater than the start value.

Example

Use recursion to add all of the numbers between 5 to 10

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}