Recursion and Subsequences

Key Concepts

• Recursion: Practice of a function calling itself.
• Subsequence: A sequence derived from another sequence where elements follow the initial sequence order. Can be contiguous or non-contiguous.
• Subarray: A contiguous part of an array.

Subsequence Definition and Examples

• Subsequence can be formed by picking elements while maintaining their order.
• Example given an array [3, 1, 2]:
  • Subsequence examples: [3], [1], [2], [3, 1], [1, 2], [3, 2], [3, 1, 2], [] (empty set).
  • Note: [3, 2] is a non-contiguous subsequence.

Power Set Algorithm

• Power Set: Method to generate all possible subsequences.
• In this lesson, focus is on using recursion to find subsequences, not the power set algorithm.

Recursive Approach Explanation

• Pattern Recognition: For each element, decide to take or not take.
• Example: Given [3, 1, 2], to form subsequence [3, 2]:
  • Take 3, do not take 1, take 2.
  • This gives us indices: take, don’t take, take.
• Use a recursive function to explore both possibilities (take or not take) at each index.

Recursive Function Breakdown

• Base Case: If index equals array length, print the current subsequence and return.
• Recursive Case:
  • Include the current element in subsequence.
  • Exclude the current element in subsequence.
• Backtracking: After exploring both possibilities, remove the element (backtrack) to explore new subsequences.

Example Code Structure

public void printSubsequences(int index, List<Integer> ds, int[] arr, int n) {
    // Base Case
    if (index == n) {
        System.out.println(ds);
        return;
    }
    
    // Include current element
    ds.add(arr[index]);
    printSubsequences(index + 1, ds, arr, n);
    
    // Exclude current element (backtrack)
    ds.remove(ds.size() - 1);
    printSubsequences(index + 1, ds, arr, n);
}

Recursion Tree Illustration

• Visually understand using a recursion tree.
• Example f(0, []) for [3, 1, 2] will expand with each index decided to take or not.
• Illustrated tree helps in understanding the recursive calls and backtracking.

Time and Space Complexity

• Time Complexity: 2^n * n (2 choices for each index, multiplied by n for printing).
• Space Complexity: O(n) (maximum depth of the recursion stack is n).

Summary

• Remember to use the pattern of pick and not-pick for recursion problems involving subsequences.
• Always ensure to backtrack by removing elements after recursive calls.
• Understand recursive function structure for solving more advanced problems in future.
• Practice by drawing recursion trees to improve understanding.

Example Output

3 1 2
3 1
3 2
3
1 2
1
2

Note: Maintain the order in subsequences to ensure correctness.