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

Introduction

In this tutorial, we will explore how to use recursion to solve two common problems in programming: reversing an array and checking if a string is a palindrome. Understanding these concepts is fundamental in data structures and algorithms, especially for those preparing for coding interviews or looking to enhance their problem-solving skills.

Step 1: Reverse an Array Using Recursion

To reverse an array recursively, we will use a two-pointer approach. Here’s how to implement it:

1.1 Define the Function

• Create a function that takes the array and two indices, l (left pointer) and r (right pointer).

1.2 Base Case

• If l is greater than or equal to r, return from the function. This condition indicates that we've finished swapping elements.

1.3 Swap Elements

• Swap the elements at indices l and r.

array[l], array[r] = array[r], array[l]

1.4 Recursive Call

• Call the function again, incrementing l and decrementing r:

reverse_array(array, l + 1, r - 1)

1.5 Example Code

Here’s a complete implementation in Python:

def reverse_array(array, l, r):
    if l >= r:
        return
    array[l], array[r] = array[r], array[l]
    reverse_array(array, l + 1, r - 1)

# Usage
arr = [1, 2, 3, 4, 5]
reverse_array(arr, 0, len(arr) - 1)
print(arr)  # Output: [5, 4, 3, 2, 1]

Step 2: Check If a String is a Palindrome

Next, we will write a recursive function to check if a given string is a palindrome.

2.1 Define the Function

• Create a function that accepts the string and an index i.

2.2 Base Case

• If i is greater than or equal to half the length of the string, return True. This means all relevant checks have been made.

2.3 Check Characters

• Compare the characters at positions i and n - i - 1 (where n is the length of the string). If they are not equal, return False.

2.4 Recursive Call

• If they are equal, call the function again with i + 1.

2.5 Example Code

Here’s how to implement this in Python:

def is_palindrome(s, i=0):
    n = len(s)
    if i >= n // 2:
        return True
    if s[i] != s[n - i - 1]:
        return False
    return is_palindrome(s, i + 1)

# Usage
print(is_palindrome("madam"))  # Output: True
print(is_palindrome("hello"))  # Output: False

Conclusion

In this tutorial, we've learned how to reverse an array and check if a string is a palindrome using recursion. These techniques are not only useful for understanding recursion better but also serve as foundational skills for solving more complex problems in algorithms. As you practice, try to optimize these functions further and explore how they can be applied in different contexts. Happy coding!