Master Recursion: Array Sum and Linked List Deletion Explained with Java Code

Recursion Basics with an Array Sum Example

Given an array arr = {1, 3, 6}, the goal is to compute the total sum using recursion. The problem is broken down into smaller sub‑problems where each step records the first element and delegates the sum of the remaining elements to the next recursive call.

The recursion proceeds as follows: A handles element 1, B handles {3,6}, C handles {6}, and D encounters an empty array, returning 0. Each level adds its recorded element to the result returned by the deeper call, ultimately yielding the total sum 10.

Conditions a Recursive Algorithm Must Satisfy

1. Divide the problem into smaller sub‑problems that share the same solving strategy. In the array‑sum case, each sub‑problem computes the sum of the first element plus the sum of the rest.

2. Provide a termination condition. Here the base case is when the starting index equals the array length, meaning no elements remain to be summed.

Java Implementation for Array Sum

// begin indicates the starting index in the array
// when begin == arr.length, there are no remaining elements
if (begin == arr.length) {
    return 0;
}

arr[begin] + sum(begin + 1, arr);

public int sum(int[] arr) {
    return sum(0, arr);
}

private int sum(int begin, int[] arr) {
    if (begin == arr.length) {
        return 0;
    }
    return arr[begin] + sum(begin + 1, arr); // recursive call
}

Linked List’s Natural Recursion

A linked list can be recursively defined as a head node followed by a sub‑list. This property makes it ideal for recursive algorithms such as the LeetCode #203 "Remove Linked List Elements" problem.

Problem Description (LeetCode #203)

Task: Delete all nodes with value val from a singly linked list. Example: Input: 1→2→6→3→4→5→6, val = 6; Output: 1→2→3→4→5

Recursive Solution Overview

The algorithm recursively processes the list: each call removes the target value from the remainder of the list, then decides whether to keep or discard the current head based on its value.

Java Implementation for Removing Elements

public ListNode removeElements(ListNode head, int val) {
    // base case
    if (head == null) {
        return null;
    }
    // recursively process the rest of the list
    ListNode result = removeElements(head.next, val);
    // decide whether to keep the current node
    if (head.val == val) {
        return result;
    } else {
        head.next = result;
        return head;
    }
}

This implementation follows the two recursive conditions: the problem is divided into identical sub‑problems (processing the tail of the list), and the recursion stops when the list becomes empty.

Key Takeaways

Recursion requires a clear base case and a uniform sub‑problem formulation.

Array sum and linked‑list manipulation are classic examples that illustrate how recursion simplifies problem decomposition.

The provided Java code can be directly used or adapted for similar recursive challenges.