Recursion and Backtracking: Problems on Functional Recursion

This chapter covers foundational problems solved using functional recursion. We examine how to reverse an array and how to verify whether a string is a palindrome using recursive strategies, moving from two-pointer approaches to optimized single-variable approaches.

1. Why Do We Need Functional Recursion for Arrays and Strings?

When iterating through data structures like arrays or strings iteratively, we typically use for or while loops with pointers starting from both ends (l and r) and moving toward the center.

However, recursive formulations allow us to break these problems down into smaller, self-similar sub-problems. Functional recursion specifically allows a function to compute a result, make a recursive call for the next sub-problem, and pass or return boolean/void states cleanly without relying on global mutable state.

2. Core Mental Model: The Two-Pointer Iterative vs. Recursive Analogy

Real-Life Analogy

Imagine two people standing at opposite ends of a long line of numbered boxes (an array).

1. Person L stands at the far left; Person R stands at the far right.
2. They pick up the items in front of them, swap their positions, and take one step inward toward each other (L + 1 and R - 1).
3. They repeat this operation until they cross paths or meet in the middle.

In recursion, instead of writing a loop to manage this walk, each function call represents one single step of swapping and delegating the next step to the subsequent recursive call.

3. Reversing an Array Using Two Pointers

The Strategy

We maintain two indices, l (left) and r (right). The base case states that when l crosses or equals r, all elements have been swapped, and we return. Otherwise, we swap array[l] and array[r], then invoke the recursive function for the next inward indices.

C++ Code Implementation

#include <iostream>
#include <vector>
using namespace std;

void reverseArray(int l, int r, vector<int>& arr) {
    // Base Case: If left pointer crosses or meets right pointer, stop
    if (l >= r) return;
    
    // Task: Swap elements at index l and r
    swap(arr[l], arr[r]);
    
    // Recursive Call: Move inward
    reverseArray(l + 1, r - 1, arr);
}

int main() {
    vector<int> arr = {1, 3, 2, 5, 4};
    int n = arr.size();
    
    reverseArray(0, n - 1, arr);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

4. Optimizing to a Single Variable (i)

Carrying two separate pointers (l and r) is unnecessary because r can always be mathematically derived from l and the total size n.

The Derivation

For any given index i (acting as our left pointer), its corresponding counterpart from the right end is:

• Example: If $n = 5$,
  • When $i = 0$, counterpart is $5 - 0 - 1 = 4$
  • When $i = 1$, counterpart is $5 - 1 - 1 = 3$

Furthermore, we only need to iterate up to the middle of the array. Thus, our base case changes from $l \ge r$ to $i \ge \frac{n}{2}$.

C++ Code with Single Variable i

#include <iostream>
#include <vector>
using namespace std;

void reverseSingleVar(int i, vector<int>& arr, int n) {
    // Base Case: Stop when we cross the middle of the array
    if (i >= n / 2) return;
    
    // Task: Swap arr[i] with its mirrored counterpart from the right
    swap(arr[i], arr[n - i - 1]);
    
    // Recursive Call: Increment i
    reverseSingleVar(i + 1, arr, n);
}

int main() {
    vector<int> arr = {1, 3, 2, 5, 4};
    int n = arr.size();
    
    reverseSingleVar(0, arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

5. Problem: Check if a String is a Palindrome

Definition of a Palindrome

A palindrome is a string that reads the same forwards and backwards (e.g., "madam", "11211").

Connecting Palindromes to Reversal Logic

If a string on reversal remains identical to its original form, the characters in the left half must mirror the characters in the right half:

• s[0] == s[n - 1]
• s[1] == s[n - 2]
• and so on, up to the middle.

Instead of swapping characters like we did in the array reversal, we check for equality. If any mirrored pair fails to match, we immediately return false. If we successfully reach the middle without mismatches, we return true.

6. Step-by-Step Palindrome Walkthrough

Let's trace the function f(i) checking the string "madam" ($n = 5$):

Non-Palindromic Trace ("mad" / mismatch case):

If we check "mat" ($n = 3$):

• f(0) checks s[0] == s[2] ('m' == 't') -> Mismatch!
• Immediately returns false without making any further recursive calls. Short-circuiting saves unnecessary checks.

7. Complete Palindrome Code Implementation

#include <iostream>
#include <string>
using namespace std;

bool checkPalindrome(int i, string& s) {
    int n = s.size();
    
    // Base Case: If pointer reaches or crosses the middle, all checks passed
    if (i >= n / 2) return true;
    
    // Condition Check: If characters at mirrored positions do not match
    if (s[i] != s[n - i - 1]) return false;
    
    // Recursive Call: Check the next index inward
    return checkPalindrome(i + 1, s);
}

int main() {
    string s1 = "madam";
    string s2 = "match";
    
    cout << s1 << " is palindrome? " << (checkPalindrome(0, s1) ? "Yes" : "No") << endl;
    cout << s2 << " is palindrome? " << (checkPalindrome(0, s2) ? "Yes" : "No") << endl;
    
    return 0;
}

8. Complexity Analysis

Summary and Key Takeaways

• Functional Recursion Paradigm: Unlike void functions that perform side-effects only, functional recursive methods return specific values (like booleans or computed states) up the call stack.
• State Reduction via Math: Multi-pointer tracking (l and r) can be streamlined into a single index variable i by expressing the opposite pointer as n - i - 1.
• Base Case for Middle Crossings: For symmetric array and string operations, recursion terminates when the pointer reaches halfway through the data structure ($i \ge \frac{n}{2}$).
• Palindrome Verification Logic: Checking palindromes mirrors the array reversal logic, replacing the swap() operation with an equality check s[i] == s[n - i - 1].
• Early Exit (Short-circuiting): In the palindrome check, finding a single character mismatch immediately returns false, preventing redundant checks down the recursion stack.
• Reference Passing: Passing vectors and strings by reference (vector<int>& arr, string& s) avoids costly object copying across recursive stack frames.
• Complexity Profile: Both problems operate in $O(n)$ time complexity and consume $O(n)$ auxiliary stack space due to recursion depth.