RecursiveTask and RecursiveAction in Java

In Java, when dealing with concurrent programming it is often required to divide a task into subtasks and execute them concurrently. The RecursiveTask and RecursiveAction classes in the java.util.concurrent package provide a convenient way to achieve this.

RecursiveTask

The RecursiveTask class is an abstract class that represents a task that returns a result. It can be used when a task needs to be divided into subtasks of the same type and the results of those subtasks need to be combined.

To use RecursiveTask, you need to extend the class and implement the compute() method. This method is responsible for dividing the task into smaller subtasks and computing the result. The compute() method returns the result of the task.

Here is an example that calculates the sum of an array using RecursiveTask:

import java.util.concurrent.*;

public class SumTask extends RecursiveTask<Integer> {
    private final int[] array;
    private final int start;
    private final int end;

    public SumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    public Integer compute() {
        if (end - start <= 100) {
            int sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask leftSubtask = new SumTask(array, start, mid);
            SumTask rightSubtask = new SumTask(array, mid, end);

            leftSubtask.fork();
            rightSubtask.fork();

            int leftResult = leftSubtask.join();
            int rightResult = rightSubtask.join();

            return leftResult + rightResult;
        }
    }
}

In the above example, the compute() method divides the array into two subarrays and creates two new SumTask instances to compute the sum of each subarray. The fork() method is used to submit the subtasks for execution in parallel, and the join() method is used to retrieve the results of the subtasks and combine them.

To execute the SumTask, you can create an instance and submit it to an ExecutorService as follows:

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
SumTask sumTask = new SumTask(array, 0, array.length);
ForkJoinPool forkJoinPool = new ForkJoinPool();
int result = forkJoinPool.invoke(sumTask);
System.out.println("Sum: " + result);

RecursiveAction

The RecursiveAction class is similar to RecursiveTask but doesn't return a result. It is used when a task needs to be divided into subtasks that don't produce a result, for example, tasks that perform some computation or tasks that update shared data.

To use RecursiveAction, you also need to extend the class and implement the compute() method. This method is responsible for dividing the task into smaller subtasks and performing the actual computation.

Here is an example that divides an array by two for several iterations using RecursiveAction:

import java.util.concurrent.*;

public class ArrayDivideTask extends RecursiveAction {
    private final int[] array;
    private final int start;
    private final int end;

    public ArrayDivideTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if (end - start <= 100) {
            for (int i = start; i < end; i++) {
                array[i] /= 2; // Divide each element by 2
            }
        } else {
            int mid = (start + end) / 2;
            ArrayDivideTask leftSubtask = new ArrayDivideTask(array, start, mid);
            ArrayDivideTask rightSubtask = new ArrayDivideTask(array, mid, end);

            leftSubtask.fork();
            rightSubtask.fork();

            leftSubtask.join();
            rightSubtask.join();
        }
    }
}

In the above example, the compute() method divides the array into two subarrays and creates two new ArrayDivideTask instances to divide each subarray. The results of the subtasks are obtained using the join() method.

To execute the ArrayDivideTask, you can create an instance and submit it to an ExecutorService like this:

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
ArrayDivideTask divideTask = new ArrayDivideTask(array, 0, array.length);
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(divideTask);
System.out.println("Resulting Array: " + Arrays.toString(array));

The above code creates an instance of ArrayDivideTask and invokes it using a ForkJoinPool. The resulting modified array is printed, showing the elements divided by 2.

Conclusion

The RecursiveTask and RecursiveAction classes provide a powerful mechanism for dividing tasks into subtasks and executing them concurrently. By taking advantage of the ForkJoinPool, you can leverage the available computing resources more efficiently and achieve higher performance in your concurrent Java applications.