1. Overview

RecursiveTask and RecursiveAction are abstract classes in the Fork/Join framework designed for parallelizing recursive algorithms.

Key Differences

RecursiveTask	RecursiveAction
Returns a result	No result returned
Extends ForkJoinTask<V>	Extends ForkJoinTask<Void>
compute() returns V	compute() returns void
Use for computations that produce results	Use for operations that modify state

2. RecursiveTask (Returns Result)

Basic Structure

public abstract class RecursiveTask<V> extends ForkJoinTask<V> {
protected abstract V compute();
// Other inherited methods:
// get(), join(), fork(), invoke(), etc.
}

Complete Example: Array Sum with RecursiveTask

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;
import java.util.Random;
public class ArraySumRecursiveTask extends RecursiveTask<Long> {
private final int[] array;
private final int start;
private final int end;
private static final int THRESHOLD = 1000; // Sequential computation threshold
// Public constructor for initial task
public ArraySumRecursiveTask(int[] array) {
this(array, 0, array.length);
}
// Private constructor for subtasks
private ArraySumRecursiveTask(int[] array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}
@Override
protected Long compute() {
int length = end - start;
// Base case: if problem is small enough, compute sequentially
if (length <= THRESHOLD) {
return computeSequentially();
}
// Recursive case: split problem and fork subtasks
int mid = start + (length / 2);
ArraySumRecursiveTask leftTask = new ArraySumRecursiveTask(array, start, mid);
ArraySumRecursiveTask rightTask = new ArraySumRecursiveTask(array, mid, end);
// Fork the left task (execute asynchronously)
leftTask.fork();
// Compute right task in current thread
Long rightResult = rightTask.compute();
// Wait for left task to complete and get result
Long leftResult = leftTask.join();
// Combine results
return leftResult + rightResult;
}
private Long computeSequentially() {
long sum = 0;
for (int i = start; i < end; i++) {
sum += array[i];
}
System.out.println(Thread.currentThread().getName() + 
" computed range " + start + " to " + (end-1));
return sum;
}
public static void main(String[] args) {
// Create test data
int[] array = createTestArray(100000);
// Create ForkJoinPool
ForkJoinPool pool = ForkJoinPool.commonPool();
// Create task
ArraySumRecursiveTask task = new ArraySumRecursiveTask(array);
// Execute and get result
long startTime = System.currentTimeMillis();
Long result = pool.invoke(task);
long endTime = System.currentTimeMillis();
// Verify result
long sequentialSum = computeSequentially(array);
System.out.println("Parallel result: " + result);
System.out.println("Sequential result: " + sequentialSum);
System.out.println("Results match: " + (result.equals(sequentialSum)));
System.out.println("Time taken: " + (endTime - startTime) + "ms");
System.out.println("Pool parallelism: " + pool.getParallelism());
}
private static int[] createTestArray(int size) {
int[] array = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(100);
}
return array;
}
private static long computeSequentially(int[] array) {
long sum = 0;
for (int value : array) {
sum += value;
}
return sum;
}
}

Advanced RecursiveTask: Matrix Multiplication

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;
public class MatrixMultiplicationTask extends RecursiveTask<int[][]> {
private final int[][] matrixA;
private final int[][] matrixB;
private final int rowStart;
private final int rowEnd;
private final int colStart;
private final int colEnd;
private static final int THRESHOLD = 64; // Threshold for sequential computation
public MatrixMultiplicationTask(int[][] matrixA, int[][] matrixB) {
this(matrixA, matrixB, 0, matrixA.length, 0, matrixB[0].length);
}
private MatrixMultiplicationTask(int[][] matrixA, int[][] matrixB, 
int rowStart, int rowEnd, int colStart, int colEnd) {
this.matrixA = matrixA;
this.matrixB = matrixB;
this.rowStart = rowStart;
this.rowEnd = rowEnd;
this.colStart = colStart;
this.colEnd = colEnd;
}
@Override
protected int[][] compute() {
int rows = rowEnd - rowStart;
int cols = colEnd - colStart;
// If the submatrix is small enough, compute sequentially
if (rows <= THRESHOLD && cols <= THRESHOLD) {
return computeSequentially();
}
// Split along rows if more rows than columns, otherwise split along columns
if (rows >= cols) {
int midRow = rowStart + rows / 2;
MatrixMultiplicationTask topTask = new MatrixMultiplicationTask(
matrixA, matrixB, rowStart, midRow, colStart, colEnd);
MatrixMultiplicationTask bottomTask = new MatrixMultiplicationTask(
matrixA, matrixB, midRow, rowEnd, colStart, colEnd);
topTask.fork();
int[][] bottomResult = bottomTask.compute();
int[][] topResult = topTask.join();
return combineResults(topResult, bottomResult, rows, cols);
} else {
int midCol = colStart + cols / 2;
MatrixMultiplicationTask leftTask = new MatrixMultiplicationTask(
matrixA, matrixB, rowStart, rowEnd, colStart, midCol);
MatrixMultiplicationTask rightTask = new MatrixMultiplicationTask(
matrixA, matrixB, rowStart, rowEnd, midCol, colEnd);
leftTask.fork();
int[][] rightResult = rightTask.compute();
int[][] leftResult = leftTask.join();
return combineResults(leftResult, rightResult, rows, cols);
}
}
private int[][] computeSequentially() {
int rows = rowEnd - rowStart;
int cols = colEnd - colStart;
int[][] result = new int[rows][cols];
for (int i = rowStart; i < rowEnd; i++) {
for (int j = colStart; j < colEnd; j++) {
for (int k = 0; k < matrixB.length; k++) {
result[i - rowStart][j - colStart] += matrixA[i][k] * matrixB[k][j];
}
}
}
return result;
}
private int[][] combineResults(int[][] part1, int[][] part2, int rows, int cols) {
int[][] combined = new int[rows][cols];
// Determine how to combine based on split direction
if (part1.length == rows && part2.length == rows) {
// Split was along columns
int splitPoint = part1[0].length;
for (int i = 0; i < rows; i++) {
System.arraycopy(part1[i], 0, combined[i], 0, splitPoint);
System.arraycopy(part2[i], 0, combined[i], splitPoint, part2[i].length);
}
} else {
// Split was along rows
int splitPoint = part1.length;
for (int i = 0; i < splitPoint; i++) {
System.arraycopy(part1[i], 0, combined[i], 0, cols);
}
for (int i = 0; i < part2.length; i++) {
System.arraycopy(part2[i], 0, combined[i + splitPoint], 0, cols);
}
}
return combined;
}
public static void main(String[] args) {
// Create test matrices
int size = 256;
int[][] matrixA = createMatrix(size, size, 1);
int[][] matrixB = createMatrix(size, size, 2);
ForkJoinPool pool = ForkJoinPool.commonPool();
MatrixMultiplicationTask task = new MatrixMultiplicationTask(matrixA, matrixB);
long startTime = System.currentTimeMillis();
int[][] result = pool.invoke(task);
long parallelTime = System.currentTimeMillis() - startTime;
System.out.println("Matrix multiplication completed");
System.out.println("Result matrix: " + result.length + "x" + result[0].length);
System.out.println("Parallel time: " + parallelTime + "ms");
}
private static int[][] createMatrix(int rows, int cols, int value) {
int[][] matrix = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = value;
}
}
return matrix;
}
}

3. RecursiveAction (No Result)

Basic Structure

public abstract class RecursiveAction extends ForkJoinTask<Void> {
protected abstract void compute();
// Other inherited methods:
// fork(), join(), invoke(), etc.
}

Complete Example: Array Processing with RecursiveAction

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;
import java.util.Random;
public class ArrayTransformRecursiveAction extends RecursiveAction {
private final double[] array;
private final int start;
private final int end;
private static final int THRESHOLD = 10000;
public ArrayTransformRecursiveAction(double[] array) {
this(array, 0, array.length);
}
private ArrayTransformRecursiveAction(double[] array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}
@Override
protected void compute() {
int length = end - start;
if (length <= THRESHOLD) {
transformSequentially();
return;
}
// Split the task
int mid = start + length / 2;
ArrayTransformRecursiveAction leftTask = 
new ArrayTransformRecursiveAction(array, start, mid);
ArrayTransformRecursiveAction rightTask = 
new ArrayTransformRecursiveAction(array, mid, end);
// Invoke all tasks - more efficient than separate fork/join
invokeAll(leftTask, rightTask);
// No need to combine results since we're modifying the array in place
}
private void transformSequentially() {
for (int i = start; i < end; i++) {
// Apply complex transformation
array[i] = Math.sqrt(Math.abs(Math.sin(array[i]) * Math.cos(array[i]))) + 
Math.log(Math.abs(array[i]) + 1);
}
System.out.println(Thread.currentThread().getName() + 
" transformed elements " + start + " to " + (end-1));
}
public static void main(String[] args) {
// Create test array
double[] array = createTestArray(100000);
// Create ForkJoinPool
ForkJoinPool pool = new ForkJoinPool();
// Create and execute task
ArrayTransformRecursiveAction task = new ArrayTransformRecursiveAction(array);
System.out.println("Before transformation - first 5 elements:");
printFirstElements(array, 5);
long startTime = System.currentTimeMillis();
pool.invoke(task);
long endTime = System.currentTimeMillis();
System.out.println("After transformation - first 5 elements:");
printFirstElements(array, 5);
System.out.println("Transformation completed in " + (endTime - startTime) + "ms");
}
private static double[] createTestArray(int size) {
double[] array = new double[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
array[i] = random.nextDouble() * 100 - 50; // Values between -50 and 50
}
return array;
}
private static void printFirstElements(double[] array, int count) {
for (int i = 0; i < Math.min(count, array.length); i++) {
System.out.printf("array[%d] = %.4f%n", i, array[i]);
}
}
}

Advanced RecursiveAction: Parallel QuickSort

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;
import java.util.Random;
public class ParallelQuickSortAction extends RecursiveAction {
private final int[] array;
private final int start;
private final int end;
private static final int THRESHOLD = 1000;
public ParallelQuickSortAction(int[] array) {
this(array, 0, array.length - 1);
}
private ParallelQuickSortAction(int[] array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}
@Override
protected void compute() {
if (end - start <= THRESHOLD) {
// Use sequential quicksort for small arrays
sequentialQuickSort(start, end);
return;
}
if (start < end) {
int pivotIndex = partition(start, end);
ParallelQuickSortAction leftTask = 
new ParallelQuickSortAction(array, start, pivotIndex - 1);
ParallelQuickSortAction rightTask = 
new ParallelQuickSortAction(array, pivotIndex + 1, end);
// Fork both tasks and wait for completion
invokeAll(leftTask, rightTask);
}
}
private int partition(int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(i, j);
}
}
swap(i + 1, high);
return i + 1;
}
private void sequentialQuickSort(int low, int high) {
if (low < high) {
int pivotIndex = partition(low, high);
sequentialQuickSort(low, pivotIndex - 1);
sequentialQuickSort(pivotIndex + 1, high);
}
}
private void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
// Create test array
int[] array = createTestArray(100000);
int[] arrayCopy = array.clone();
// Test parallel sort
ForkJoinPool pool = ForkJoinPool.commonPool();
ParallelQuickSortAction parallelTask = new ParallelQuickSortAction(array);
long startTime = System.currentTimeMillis();
pool.invoke(parallelTask);
long parallelTime = System.currentTimeMillis() - startTime;
// Test sequential sort for comparison
startTime = System.currentTimeMillis();
sequentialQuickSort(arrayCopy, 0, arrayCopy.length - 1);
long sequentialTime = System.currentTimeMillis() - startTime;
System.out.println("Parallel sort time: " + parallelTime + "ms");
System.out.println("Sequential sort time: " + sequentialTime + "ms");
System.out.println("Speedup: " + (double) sequentialTime / parallelTime);
System.out.println("Array sorted: " + isSorted(array));
}
private static int[] createTestArray(int size) {
int[] array = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
array[i] = random.nextInt(1000000);
}
return array;
}
private static void sequentialQuickSort(int[] array, int low, int high) {
if (low < high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
int pivotIndex = i + 1;
sequentialQuickSort(array, low, pivotIndex - 1);
sequentialQuickSort(array, pivotIndex + 1, high);
}
}
private static boolean isSorted(int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
return false;
}
}
return true;
}
}

4. Key Methods and Patterns

Fork/Join Patterns

Pattern 1: Basic Fork-Join

@Override
protected Result compute() {
if (isBaseCase()) {
return computeSequentially();
}
SubTask left = new SubTask(leftWork);
SubTask right = new SubTask(rightWork);
left.fork();           // Execute left asynchronously
Result rightResult = right.compute();  // Compute right in current thread
Result leftResult = left.join();       // Wait for left result
return combine(leftResult, rightResult);
}

Pattern 2: invokeAll (More Efficient)

@Override
protected Result compute() {
if (isBaseCase()) {
return computeSequentially();
}
List<SubTask> subtasks = createSubtasks();
invokeAll(subtasks);  // Fork all and wait for all
return combineResults(subtasks);
}

Pattern 3: Mixed Sequential/Parallel

@Override
protected Result compute() {
if (isBaseCase()) {
return computeSequentially();
}
List<SubTask> subtasks = createSubtasks();
// Process first half sequentially in current thread
for (int i = 0; i < subtasks.size() / 2; i++) {
subtasks.get(i).compute();
}
// Fork second half
for (int i = subtasks.size() / 2; i < subtasks.size(); i++) {
subtasks.get(i).fork();
}
// Join second half
for (int i = subtasks.size() / 2; i < subtasks.size(); i++) {
subtasks.get(i).join();
}
return combineResults(subtasks);
}

5. Exception Handling

import java.util.concurrent.RecursiveTask;
public class ExceptionHandlingTask extends RecursiveTask<Integer> {
private final int[] array;
private final int start;
private final int end;
public ExceptionHandlingTask(int[] array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}
@Override
protected Integer compute() {
try {
if (end - start == 1) {
if (array[start] < 0) {
throw new IllegalArgumentException("Negative value found: " + array[start]);
}
return array[start];
}
int mid = start + (end - start) / 2;
ExceptionHandlingTask leftTask = new ExceptionHandlingTask(array, start, mid);
ExceptionHandlingTask rightTask = new ExceptionHandlingTask(array, mid, end);
leftTask.fork();
int rightResult = rightTask.compute();
int leftResult = leftTask.join();
return leftResult + rightResult;
} catch (Exception e) {
// Handle exception and complete exceptionally
completeExceptionally(e);
return null;
}
}
public static void main(String[] args) {
int[] array = {1, 2, -3, 4, 5}; // Contains negative number
ForkJoinPool pool = ForkJoinPool.commonPool();
ExceptionHandlingTask task = new ExceptionHandlingTask(array, 0, array.length);
try {
Integer result = pool.invoke(task);
System.out.println("Result: " + result);
} catch (Exception e) {
System.out.println("Task failed: " + e.getMessage());
System.out.println("Cause: " + e.getCause().getMessage());
}
}
}

6. Best Practices

1. Choose Appropriate Threshold

// Good threshold calculation
private static final int THRESHOLD = 
Math.max(array.length / (Runtime.getRuntime().availableProcessors() * 4), 1000);

2. Avoid Shared Mutable State

// Good - each task works on its own data segment
private void transformSequentially() {
for (int i = start; i < end; i++) {
array[i] = transform(array[i]); // Only modifies own segment
}
}
// Bad - shared mutable state requires synchronization
private static int sharedCounter = 0; // AVOID THIS

3. Use invokeAll for Multiple Subtasks

// More efficient than sequential fork/join
@Override
protected Result compute() {
if (isBaseCase()) return computeSequentially();
List<SubTask> subtasks = createSubtasks();
invokeAll(subtasks); // Fork all at once
return combineResults(subtasks);
}

4. Balance Workload

// Split work evenly
int mid = start + (end - start) / 2;
// For uneven workloads, consider dynamic splitting
if (isWorkHeavyOnLeft()) {
// Create smaller left task and larger right task
}

7. Performance Considerations

• Threshold Tuning: Test different thresholds for optimal performance
• Task Overhead: Avoid creating too many small tasks
• Work Stealing: Let the framework balance workload automatically
• Memory Locality: Design tasks to work on contiguous memory when possible

Summary

Use RecursiveTask when:

• You need to return a result from computation
• Performing mathematical computations
• Processing data that produces output

Use RecursiveAction when:

• Modifying data structures in place
• Performing operations with side effects
• No result needs to be returned

Both classes provide an efficient way to parallelize recursive algorithms while leveraging the work-stealing capabilities of the Fork/Join framework.