Stateless vs Stateful Recursion: GroupSum vs WordSearch

Abstractum

Core Kernel Logic

The Fundamental Principle: State Locality Determines Backtracking Necessity

The critical distinction between stateless and stateful recursion is not whether state changes occur, but where those changes live and who can see them.

The Kernel:

• Stateless (GroupSum): State changes are parameter values (primitives) → each recursive call gets its own copy
• Stateful (WordSearch): State changes are shared references (arrays/objects) → all recursive calls see the same data
• Automatic cleanup vs manual cleanup is determined by state visibility scope
• Stack unwinding automatically discards local state; shared state persists until explicitly restored

The Pattern Recognition:

// STATELESS: Parameter modification creates new local copy
groupSum(start+1, target - nums[start])  // target modified locally
// When this returns, parent still has original target ✓

// STATEFUL: Reference modification affects shared data
visited[row][col] = true;  // modifies shared array
dfs(nextRow, nextCol)      // child sees this modification
// When this returns, modification persists ✗
// MUST manually restore: visited[row][col] = false;

Why This Matters:

• Stateless recursion: "Try this → fail → try that" works automatically
• Stateful recursion: "Choose this → explore → unchoose before trying that" requires manual cleanup
• The difference is memory model, not algorithmic complexity

The Meta-Pattern: If your recursive state modifications are visible to sibling calls (calls at the same recursion level), you need explicit backtracking. If modifications are isolated to each branch, the stack handles cleanup automatically.

---

The Key Difference: Local vs Shared State

Both algorithms modify something during recursion. The critical difference is where that modification lives.

---

GroupSum - Local State (Parameters)

The Code

boolean groupSum(int[] nums, int start, int target) {
    // Base case
    if (start >= nums.length)
        return target == 0;

    // Option 1: Include current number
    if (groupSum(nums, start+1, target - nums[start]))
        return true;

    // Option 2: Skip current number
    if (groupSum(nums, start+1, target))
        return true;

    return false;
}

What Happens in Memory

When you call groupSum(nums, start+1, target - nums[start]):

1. A new copy of target - nums[start] is created on the call stack
2. The parent function's target variable is unchanged
3. When this recursive call returns, you still have your original target value
4. The second call groupSum(nums, start+1, target) sees the original target, not the modified one

Visual Example

groupSum([2,4,8], 0, 10)
├─ target = 10 (original)
│
├─ Call 1: groupSum([2,4,8], 1, 8)    ← target-2 creates NEW local value
│  └─ This call has target=8 in ITS stack frame
│
└─ Call 2: groupSum([2,4,8], 1, 10)   ← original target STILL 10
   └─ This call has target=10 in ITS stack frame

Why No Manual Cleanup?

The "backtracking" happens automatically when the function returns:

• Each call has its own target value in its stack frame
• When a recursive call returns, its stack frame is destroyed
• The modified target disappears automatically
• The parent's original values remain untouched

Key Insight

Primitive types (int, boolean, char) are passed by value in Java. Each recursive call gets its own independent copy. Changes to the copy don't affect the original.

---

WordSearch - Shared State (Array Reference)

The Code

boolean dfs(char[][] board, boolean[][] visited, int row, int col, String word, int k) {
    // Bounds and validation checks
    if (row < 0 || row >= m || col < 0 || col >= n) return false;
    if (visited[row][col]) return false;
    if (board[row][col] != word.charAt(k)) return false;
    if (k == word.length() - 1) return true;

    // CHOOSE: Mark as visited
    visited[row][col] = true;  // ← Modifies the SAME array all calls share

    // EXPLORE: Try all 4 directions
    for (int[] d : DIRECTIONS) {
        if (dfs(board, visited, nextRow, nextCol, word, k+1)) {
            visited[row][col] = false;  // ← MUST manually undo
            return true;
        }
    }

    // BACKTRACK: Unmark
    visited[row][col] = false;  // ← MUST manually undo
    return false;
}

What Happens in Memory

When you set visited[row][col] = true:

1. The same array is passed by reference to all recursive calls
2. Every recursive call sees this modification
3. When the function returns, the change persists unless you explicitly undo it
4. You must manually restore visited[row][col] = false

Visual Example

All calls share the SAME visited array in memory:

visited = [[false, false],
           [false, false]]

dfs(0, 0)
├─ visited[0][0] = true
│  visited = [[TRUE, false],    ← All calls see this change
│             [false, false]]
│
├─ Call dfs(0, 1)
│  ├─ visited[0][1] = true
│  │  visited = [[TRUE, TRUE],  ← All calls see this too
│  │             [false, false]]
│  │
│  └─ When dfs(0, 1) returns, visited[0][1] is STILL true
│     UNLESS we explicitly set it back to false
│
└─ After backtracking:
   visited[0][0] = false        ← Manual cleanup required

Why Manual Cleanup?

References point to shared data:

• Arrays and objects are passed by reference in Java
• All recursive calls point to the same visited array in memory
• Modifications are visible to everyone
• When a call returns, the array still contains your modifications
• You must explicitly undo changes to restore the original state

Critical Understanding

Arrays/objects are passed by reference. All recursive calls share the same data structure. Modifications persist across calls and must be manually reverted.

---

The Core Distinction

Aspect	GroupSum (Stateless)	WordSearch (Stateful)
What's Modified	Parameter values (primitives)	Array contents (reference type)
Memory Model	Copy on call (value semantics)	Shared reference (pointer semantics)
Scope	Local to each call	Shared across all calls
Visibility	Each call has independent copy	All calls see the same data
Cleanup	Automatic via stack unwinding	Manual backtracking required
Pattern	Try option → return → try next	Choose → Explore → Unchoose
When to Undo	Never (automatic)	Always (before return)
Siblings See Changes?	No (independent copies)	Yes (shared state)

---

Deep Dive: Why the Memory Model Matters

GroupSum Memory Model

groupSum(nums, 0, 10)  // Stack frame 1: target = 10
└─ groupSum(nums, 1, 8)   // Stack frame 2: target = 8 (NEW COPY)
   └─ groupSum(nums, 2, 4)   // Stack frame 3: target = 4 (NEW COPY)

Each stack frame has its own target variable:

• Frame 1: target = 10
• Frame 2: target = 8 (independent from Frame 1)
• Frame 3: target = 4 (independent from Frame 2)

When Frame 3 returns, Frame 2's target is still 8. When Frame 2 returns, Frame 1's target is still 10.

No interference between calls.

---

WordSearch Memory Model

dfs(board, visited, 0, 0)  // Stack frame 1: visited points to Array@1234
└─ dfs(board, visited, 0, 1)  // Stack frame 2: visited ALSO points to Array@1234
   └─ dfs(board, visited, 1, 1)  // Stack frame 3: visited ALSO points to Array@1234

All stack frames point to the SAME array:

• Frame 1: visited → Array@1234
• Frame 2: visited → Array@1234 (SAME object)
• Frame 3: visited → Array@1234 (SAME object)

When Frame 3 modifies visited[1][1] = true, all frames see this change because they all point to the same array.

Direct interference between calls requires manual coordination.

---

Example: The Critical Difference

GroupSum: Automatic Cleanup

// Parent call: target = 10
if (groupSum(start+1, target - nums[start]))  // Calls with target=8
    return true;

// After the above returns (whether true or false):
// target is STILL 10 in this scope!

if (groupSum(start+1, target))  // Calls with target=10
    return true;

Why this works:

• First call gets target=8 as a new local variable
• Second call gets target=10 as a new local variable
• Both are independent; neither affects the other

---

WordSearch: Manual Cleanup Required

// Parent call: visited[0][0] currently false
visited[0][0] = true;  // Modify SHARED array

// Try direction 1
if (dfs(nextRow1, nextCol1)) {
    visited[0][0] = false;  // MUST undo before returning
    return true;
}

// Try direction 2
if (dfs(nextRow2, nextCol2)) {
    visited[0][0] = false;  // MUST undo before returning
    return true;
}

// All directions failed
visited[0][0] = false;  // MUST undo before returning
return false;

Why manual cleanup is required:

• visited[0][0] = true modifies the shared array
• Without undoing, the next direction sees visited[0][0] = true
• This blocks the second direction from using cell (0,0)
• Even though the first direction failed and abandoned (0,0), it's still marked as "used"

---

The Test: How to Identify Stateful vs Stateless

Ask yourself: "If I make a change in one recursive call, can a sibling call at the same level see that change?"

GroupSum Test

groupSum(nums, 0, 10)
├─ groupSum(nums, 1, 8)    // Modifies target to 8
└─ groupSum(nums, 1, 10)   // Can this see target=8? NO!

Answer: No → Stateless (each call has independent state)

---

WordSearch Test

dfs(0, 0)
├─ visited[0][0] = true
├─ dfs(0, 1)                   // Can this see visited[0][0]=true? YES!
└─ dfs(1, 0)                   // Can this see visited[0][0]=true? YES!

Answer: Yes → Stateful (calls share state, need backtracking)

---

Common Misconception: "GroupSum Doesn't Change State"

Wrong thinking: "GroupSum is stateless because it doesn't change anything."

Correct thinking: "GroupSum changes the target parameter, but each call gets its own copy, so changes are isolated."

The truth:

• GroupSum does modify state (the target value)
• But those modifications are local (each call's own copy)
• The modifications don't persist across sibling calls
• Therefore, no manual backtracking needed

---

The Pattern in Action

Stateless Pattern (GroupSum)

// Try option 1
if (recurse(modified_state))
    return true;

// Try option 2 (original state automatically restored)
if (recurse(original_state))
    return true;

Key: modified_state is a new value; original_state remains unchanged.

---

Stateful Pattern (WordSearch)

// Make change to shared state
state.modify();

// Try exploration
if (recurse()) {
    state.undo();  // MUST manually restore
    return true;
}

// All explorations failed
state.undo();  // MUST manually restore
return false;

Key: state.modify() affects shared data; must explicitly undo().

---

Summary

Essential Understanding

The Problem: When do recursive algorithms require explicit backtracking?

Why It Matters:

• Wrong pattern = subtle bugs (state pollution between branches)
• Right pattern = clean, correct exploration of possibility space

The Core Insight: State Visibility Determines Backtracking Necessity

Stateless Recursion (GroupSum):

• State changes: Parameter values (primitives, immutables)
• Scope: Local to each call (pass-by-value semantics)
• Visibility: Each call has independent copy
• Cleanup: Automatic via stack unwinding
• Pattern: Try A → Try B (original state automatically restored)
• Memory: O(n) stack depth, each frame has own variables

Stateful Recursion (WordSearch):

• State changes: Shared references (arrays, objects, globals)
• Scope: Shared across all calls (pass-by-reference semantics)
• Visibility: All calls see modifications
• Cleanup: Manual backtracking required
• Pattern: Choose → Explore → Unchoose (explicit state restoration)
• Memory: O(n) stack depth PLUS shared data structure

The Decision Rule:

Ask: "Can sibling recursive calls see each other's state modifications?"

• No → Stateless, automatic cleanup ✓
• Yes → Stateful, manual backtracking required ✗

The Memory Model Test:

// Stateless: New copy created
recurse(value + 1)     // Creates new local value
recurse(value)         // Original value unchanged ✓

// Stateful: Shared reference modified
array[i] = true        // Modifies shared array
recurse()              // All calls see this change
array[i] = false       // MUST manually undo ✗

The Meta-Pattern: When state lives in parameters (pass-by-value), the call stack manages cleanup. When state lives in shared structures (pass-by-reference), you must manage cleanup manually through backtracking.

Complexity Implications: Both approaches have same time complexity (explore same search space), but:

• Stateless: Simpler code, automatic cleanup, can't share work between calls
• Stateful: Requires discipline, manual cleanup, enables sharing structures between calls

One-Sentence Core: Stateless recursion uses isolated parameter copies with automatic cleanup, while stateful recursion uses shared references requiring explicit backtracking to prevent state pollution between exploration branches.

---

Key Takeaways

Remember

1. Memory model determines pattern - Value types → stateless, reference types → stateful
2. Sibling visibility test - Can parallel branches see each other's changes?
3. GroupSum is stateless - Each call has independent target value
4. WordSearch is stateful - All calls share the same visited array
5. Stack unwinding is automatic - Local variables disappear when function returns
6. Reference persistence is manual - Shared data persists until explicitly restored
7. Choose your state scope wisely - Parameters for isolation, references for sharing
8. Trust the pattern - Stateless = try/try, Stateful = choose/explore/unchoose

---

Practice Exercise

Classify these scenarios as stateless or stateful:

Scenario 1:

boolean findPath(int[] path, int index, int target) {
    if (explore(path, index+1, target-path[index])) return true;
    if (explore(path, index+1, target)) return true;
}

• Stateless
• Stateful
• Why?

Scenario 2:

boolean findPath(boolean[] used, int index) {
    used[index] = true;
    if (explore(used, index+1)) {
        used[index] = false;
        return true;
    }
    used[index] = false;
}

• Stateless
• Stateful
• Why?

Scenario 3:

boolean findPath(String currentPath, int index) {
    if (explore(currentPath + "L", index+1)) return true;
    if (explore(currentPath + "R", index+1)) return true;
}

• Stateless
• Stateful
• Why? (Tricky: Strings are immutable in Java!)

Answers:

1. Stateless - target is primitive, each call gets own copy
2. Stateful - used array is shared reference, needs manual backtracking
3. Stateless - String concatenation creates new String objects (immutable), each call gets independent copy