JavaRecursion

Java Recursion

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

Recursion may be a bit difficult to understand. Thebest way to figure out how it works is to experiment with it.

Recursion Example

Adding two numbers together is easy to do, but adding a range of numbers is morecomplicated. In the following example, recursion is used to add a range of numberstogether by breaking it down into the simple task of adding two numbers:

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

Example Explained

When thesum() method is called, it adds parameterk to the sum of all numbers smallerthank and returns the result. Whenk becomes 0, the method just returns 0. Whenrunning, the program follows these steps:

Since the method does not call itself whenk is 0, the program stops there and returns theresult.

Halting Condition

Just as loops can run into the problem of infinite looping, recursive methods can run intothe problem of infinite recursion. Infinite recursion is when the method never stops callingitself. Every recursive method should have a halting condition, which is the conditionwhere the method stops calling itself. In the previous example, the halting condition iswhen the parameterk becomes 0.

It is helpful to see a variety of different examples to better understand the concept. In thisexample, the method adds a range of numbers between a start and an end. The haltingcondition for this recursive method is whenend is not greater thanstart:

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

Countdown with Recursion

This example demonstrates how to use recursion to create a countdown function:

public class Main {  static void countdown(int n) {    if (n > 0) {      System.out.print(n + " ");      countdown(n - 1);    }  }  public static void main(String[] args) {    countdown(5);  }}

The method calls itself withn - 1 untiln becomes0.

Calculate Factorial with Recursion

This example uses a recursive method to calculate the factorial of 5:

public class Main {  static int factorial(int n) {    if (n > 1) {      return n * factorial(n - 1);    } else {      return 1;    }  }  public static void main(String[] args) {    System.out.println("Factorial of 5 is " + factorial(5));  }}