Recursion and Backtracking - (Theory)

1. What Is Recursion?

Recursion is a problem-solving paradigm where a function calls itself with a different state or a different portion of the problem.

Key Insight:
Recursion is not just about reducing input — it's about making decisions based on the choices available at the current state.
The input size often reduces as a consequence of making these decisions.

How It Works Conceptually

At every point:

• You look at the current input and current state.

• You make a decision based on the choices available.

• Each decision leads to a new state (and often a smaller input).

• You solve the smaller subproblems recursively.

Example: In a subset-sum problem, you don’t just reduce the array. You choose to include or exclude the current element — that's a decision, not just a size reduction.

2. The Induction - Base - Hypothesis Method (IBH)

This is a structured way to think about recursion and induction.

1. Base Case

This is the simplest version of the problem — where the answer is known directly.
This prevents infinite recursion.

Example:
In factorial(n), n == 0 or n == 1 is the base case → return 1.

2. Hypothesis

Assume that your recursive function works correctly for smaller inputs.
This is a mental model, not code.

Example:
Suppose factorial(n-1) gives you the correct answer — trust that assumption.

3. Induction Step (Build)

Use the result from the smaller input (from the hypothesis) to build the answer for the current input.

Example:
factorial(n) = n * factorial(n-1)
You use the hypothesis for n-1 to compute for n.

This mirrors mathematical induction and helps develop and verify recursive logic.

3. Input - Output Method (Stateful Recursion)

This method models the recursive problem with two key components:

• Input (Function Parameters): The data you pass to the function.

• Output (Return value or state changes): The result or the action at that point.

How it works:

• You define a recursive function with meaningful input parameters.

• Each call transforms input → modifies state → outputs a result (or leads to further calls).

• You make choices at each point → That determines how the input changes for next call.

4. Include / Exclude Pattern (Decision Tree Recursion)

This is a classic pattern in problems like:

• Subset generation

• Subset sum

• Combinations

Decision at every step:

• Include the current element → move to next index with updated state

• Exclude the current element → move to next index without updating the state

This builds a recursion tree of all possible decisions.

Recursive Tree Visualization

Let’s say arr = [1, 2, 3], and we want to generate subsets:

At index 0 (arr[0] = 1):

                         []
                  /             \
             [1]                []
           /     \           /     \
       [1,2]   [1]      [2]     []
       /   \    / \      / \     / \
[1,2,3]...etc

Each level of the tree represents a decision point (include or exclude).
This is why we say recursion explores the decision space.

5. Time Complexity of Recursive Algorithms

To analyze recursion, use this formula:

General Formula:

Total Time = Number of Calls × Work per Call
           = (Branching Factor ^ Depth) × Work per Call

Or,

T(n) = (Calls^Depth) + (Depth × Work Per Call)

Examples:

Fibonacci (Naive)

fib(n) = fib(n-1) + fib(n-2)

• Branching factor: 2

• Depth: n

• Time: O(2^n)

Subset Generation

void helper(int idx, List<Integer> path) {
    if (idx == n) return;
    // include
    path.add(arr[idx]);
    helper(idx+1, path);
    path.remove(path.size() - 1);
    // exclude
    helper(idx+1, path);
}

• Branching factor: 2

• Depth: n

• Time: O(2^n)

6. Common Recursive Problem Types

1. Backtracking (Recursive with Constraint)

Recursion + Choice + Constraint → Explore and backtrack.

✅ Subsets
✅ Palindrome Partitioning
✅ N-Queens

2. Divide and Conquer

Divide the input → Recursively solve → Combine the results

✅ Merge Sort
✅ Quick Sort
✅ Binary Search
✅ Maximum Subarray (Kadane's with Divide & Conquer)

3. Tree Recursion (Multiple calls per node)

Each recursive call leads to two or more further recursive calls.

✅ Fibonacci
✅ Generate Parentheses
✅ Recursion Trees (Subset, Combination, etc.)

7. Example – Subset Sum

void solve(int[] arr, int idx, int sum, int target) {
    if (idx == arr.length) {
        if (sum == target) System.out.println("Found");
        return;
    }

    // include
    solve(arr, idx + 1, sum + arr[idx], target);

    // exclude
    solve(arr, idx + 1, sum, target);
}

Recursion Tree:

• At each level, two calls → include/exclude.

• Total nodes = 2^n

• Time Complexity = O(2^n)

• Depth = n

• Work per call = O(1)

• Total Work = O(2^n)

8. Recursion vs Iteration

Final Thoughts

• Think recursively in terms of:

  • Current input

  • Choices available

  • Result of those choices

• Don’t aim to shrink the input — aim to decide and progress based on state.

• Induction-Hypothesis-Base helps build and verify recursive functions.

• Input/Output and Include/Exclude methods give structured ways to build recursive logic.

• Use recursive tree visualization to understand branching and time complexity.

• Use the Calls^Depth × Work per Call formula for complexity estimation.