Re 4. Problems on Functional Recursion | Strivers A2Z DSA Course
Table of Contents
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) andr
(right pointer).
1.2 Base Case
- If
l
is greater than or equal tor
, return from the function. This condition indicates that we've finished swapping elements.
1.3 Swap Elements
- Swap the elements at indices
l
andr
.
array[l], array[r] = array[r], array[l]
1.4 Recursive Call
- Call the function again, incrementing
l
and decrementingr
:
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, returnTrue
. This means all relevant checks have been made.
2.3 Check Characters
- Compare the characters at positions
i
andn - i - 1
(wheren
is the length of the string). If they are not equal, returnFalse
.
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!