Tail-Recursive List Length

Problem Statement

Write a Java program that computes the length of a singly linked list using a tail-recursive method with an accumulator to track the count of nodes. The program should also implement an iterative method to compute the length for comparison. Test both approaches with lists of varying sizes, including empty lists and single-node lists, and compare their readability and performance. You can visualize this as counting the number of links in a chain, either by recursively passing the count to the next link (tail-recursive) or by iteratively stepping through each link (iterative).

Input: A singly linked list with integer nodes (e.g., 1 -> 2 -> 3 -> null). Output: An integer representing the number of nodes in the list (e.g., 3 for 1 -> 2 -> 3 -> null). Constraints:

• The list contains 0 to 10^5 nodes.
• Node values are integers between -10^9 and 10^9.
• The list may be empty. Example:
• Input: Linked list 1 -> 2 -> 3 -> null
• Output: 3
• Explanation: The list has 3 nodes.
• Input: Empty linked list null
• Output: 0
• Explanation: An empty list has no nodes.

Pseudocode

FUNCTION tailRecursiveLength(node, accumulator)
    IF node is null THEN
        RETURN accumulator
    ENDIF
    SET newAccumulator to accumulator + 1
    RETURN tailRecursiveLength(node.next, newAccumulator)
ENDFUNCTION

FUNCTION iterativeLength(node)
    SET count to 0
    SET current to node
    WHILE current is not null
        INCREMENT count
        SET current to current.next
    ENDWHILE
    RETURN count
ENDFUNCTION

FUNCTION mainLength(head)
    CALL tailRecursiveLength(head, 0)
    CALL iterativeLength(head)
    RETURN results
ENDFUNCTION

Algorithm Steps

1. For the tail-recursive approach: a. Define a tail-recursive helper function that takes the current node and an accumulator as parameters. b. Implement the base case: if the node is null, return the accumulator. c. For the recursive case, increment the accumulator by 1 and recursively call the function with the next node and the updated accumulator. d. Call the helper function with the head node and an initial accumulator of 0.
2. For the iterative approach: a. Initialize a counter to 0 and a pointer current to the head of the list. b. While current is not null, increment the counter and move current to the next node. c. Return the counter as the list length.
3. In the main function, call both the tail-recursive and iterative methods to compute the list length.
4. Compare readability (recursive is more concise but abstract; iterative is more explicit) and performance (iterative is more space-efficient).

Java Implementation

public class TailRecursiveListLength {
    // Node class for singly linked list
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Computes list length using tail recursion
    public int tailRecursiveLength(Node head) {
        // Call tail-recursive helper with initial accumulator
        return tailRecursiveLengthHelper(head, 0);
    }

    // Helper function for tail-recursive length
    private int tailRecursiveLengthHelper(Node node, int accumulator) {
        // Base case: if node is null, return accumulator
        if (node == null) {
            return accumulator;
        }
        // Recursive case: increment accumulator and recurse
        return tailRecursiveLengthHelper(node.next, accumulator + 1);
    }

    // Computes list length using iteration
    public int iterativeLength(Node head) {
        // Initialize counter and current pointer
        int count = 0;
        Node current = head;
        // Iterate until null
        while (current != null) {
            count++;
            current = current.next;
        }
        // Return final count
        return count;
    }
}

Output

For the input linked list 1 -> 2 -> 3 -> null, both methods output:

3

Explanation: The list has 3 nodes.

For an empty linked list null, both methods output:

0

Explanation: An empty list has no nodes.

For a single-node linked list 4 -> null, both methods output:

1

Explanation: The list has 1 node.

How It Works

• Tail-Recursive Approach:
  • Step 1: The tailRecursiveLength method calls the helper with head and accumulator = 0.
  • Step 2: In tailRecursiveLengthHelper:
    • For node 1: accumulator = 0 + 1 = 1, recurse with node = 2, accumulator = 1.
    • For node 2: accumulator = 1 + 1 = 2, recurse with node = 3, accumulator = 2.
    • For node 3: accumulator = 2 + 1 = 3, recurse with node = null, accumulator = 3.
    • For null: Base case, return accumulator = 3.
  • Example Trace: For 1 -> 2 -> 3 -> null, the accumulator builds: 0 → 1 → 2 → 3, returning 3.
  • Tail Recursion Note: The function is tail-recursive because the recursive call is the last operation, though Java does not optimize tail recursion.
• Iterative Approach:
  • Step 1: The iterativeLength method initializes count = 0, current = head.
  • Step 2: Iterates:
    • current = 1: count = 1, move to 2.
    • current = 2: count = 2, move to 3.
    • current = 3: count = 3, move to null.
    • current = null: Return count = 3.
  • Example Trace: For 1 -> 2 -> 3 -> null, counts nodes: 1 → 2 → 3, returning 3.
• Comparison:
  • Readability: Tail-recursive is concise and elegant but may be less intuitive for beginners; iterative is straightforward and explicit.
  • Performance: Both are O(n) time, but iterative uses O(1) space, while tail-recursive uses O(n) space due to the call stack in Java.

Complexity Analysis Table

Note:

• n is the number of nodes in the linked list.
• Time complexity: O(n) for both, as each node is visited exactly once.
• Space complexity: O(n) for tail-recursive due to the call stack (Java does not optimize tail recursion); O(1) for iterative, using only a counter and pointer.
• Best, average, and worst cases are O(n) for both.

✅ Tip: Use tail recursion for elegant solutions to problems like list length, but prefer the iterative approach for large lists to save memory. Test with empty lists and long lists (e.g., 10^4 nodes) to compare performance and readability.

⚠ Warning: Java does not optimize tail recursion, so the O(n) space complexity may cause stack overflow for very large lists. Ensure the list is properly constructed to avoid null pointer exceptions.