Re 4. Problems on Functional Recursion | Strivers A2Z DSA Course

Main Ideas / Lessons Conveyed

1. Use recursion to reverse an array

   • Reversal can be achieved by swapping symmetric positions: the element at the left index with the corresponding element at the right index.
   • Recursion’s role is to perform the swap task repeatedly while shrinking the problem toward the middle.

2. Two-pointer recursion for array reversal

   • Maintain pointers l (left) and r (right).
   • Swap a[l] and a[r], then recurse on the next pair: l+1 and r-1.
   • Stop when l >= r (no more swaps needed).

3. Single-index recursion for array reversal

   • Instead of two pointers, use one index i.
   • The corresponding right index is:
     • right index = n - i - 1
   • Swap a[i] with a[n - i - 1].
   • Stop when i >= n/2 (once you reach the middle, further swaps are unnecessary).

4. Functional recursion to check if a string is palindrome

   • A string is a palindrome if it reads the same forwards and backwards.
   • In recursion, the function returns a boolean (true/false).
   • Compare symmetric characters:
     • If s[i] != s[n - i - 1], return false.
     • If they match, recursively check the next inner pair: i+1.
   • Base case: when i >= n/2, return true (all necessary checks passed).

5. Complexities

   • Array reversal:
     • Time: (O(n)) (swapping across roughly n/2 positions)
     • Space: (O(n)) due to recursion stack (depth roughly n/2)
   • Palindrome checking:
     • Time: (O(n)) (only half the string is checked)
     • Space: (O(n)) recursion stack (half-depth)

---

Methodologies / Instruction-Style Steps

A) Reverse an array using recursion with two pointers (l, r)

• Define recursive function f(l, r) where:
  • Recursion task: swap elements at positions l and r.
• Base case / stopping condition:
  • If l >= r, return (no more swaps needed).
• Recursive step:
  • Swap a[l] and a[r].
  • Call f(l + 1, r - 1) to swap the next outer pair.
• Initial call:
  • f(0, n - 1).

---

B) Reverse an array using recursion with a single pointer (i)

• Observation: for index i, the symmetric index is n - i - 1.
• Define recursive function f(i) (or f(i, a, n)):
  • Task: swap a[i] with a[n - i - 1].
• Base case / stopping condition:
  • If i >= n/2, return (middle reached; reversal complete).
• Recursive step:
  • Swap a[i] and a[n - i - 1].
  • Call f(i + 1).
• Initial call:
  • f(0).

---

C) Check if a string is palindrome using functional recursion

• Define a boolean recursive function f(i) returning:
  • true if substring/pairs from i onward are palindromic
  • false otherwise
• Base case / stopping condition:
  • If i >= n/2, return true (all required symmetric comparisons succeeded).
• Recursive check:
  • If s[i] != s[n - i - 1], return false.
  • Else return f(i + 1).
• Initial call:
  • f(0).

---

Speakers / Sources Featured

• No other speakers/sources are explicitly identified.
• The video is presented by an instructor/host (Striver, “Strivers A2Z DSA Course”), but the specific individual speaker name is not stated in the subtitles.