Problem Statement
The task is to determine if a given string is a palindrome using recursion.
Definition
- A palindrome is a word, phrase, or sequence that reads the same backwards as forwards, ignoring spaces, punctuation, and capitalization.
- Example: For the input "racecar", the output should be true because "racecar" is the same when read backwards.
Example Inputs
- Input: "racecar"
- Output: true
Explanation: The string "racecar" is a palindrome because it reads the same forwards and backwards.
Approach - Use Recursion
Approach
To check if a string is a palindrome, we can use a recursive approach. The idea is to compare the first and last characters of the string. If they are the same, we recursively check the substring formed by removing the first and last characters. If at any point the characters don't match, the string is not a palindrome.
Steps
- Base Case: If the string has 0 or 1 character, it is a palindrome (since a single character or an empty string is trivially a palindrome).
- Compare the first and last characters of the string.
- If the characters match, recursively check the substring (i.e., remove the first and last characters).
- If the characters don't match, return false (not a palindrome).
- Continue the process until the base case is reached.
Time & Space Complexity
- Time Complexity: O(n), where
n is the length of the string. We check each character at most once.
- Space Complexity: O(n), due to the recursion stack. Each recursive call adds a layer to the stack.
Code Snippet
Dry Run
Let’s dry run the code with the input str = "racecar":
- isPalindrome("racecar"): Compare "r" and "r", they match.
- isPalindrome("aceca"): Compare "a" and "a", they match.
- isPalindrome("cec"): Compare "c" and "c", they match.
- isPalindrome("e"): Base case reached, return true.
Output:
- Result: true (since "racecar" is a palindrome).
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(n), where
n is the number of characters in the string. We check each character at most once.
- Space Complexity: O(n) due to the recursion stack. Each recursive call adds a new layer to the stack.
Conclusion
The recursive approach to checking if a string is a palindrome is intuitive and easy to implement. It provides a clear and simple solution to the problem. However, recursion comes with a space overhead due to the call stack, making the space complexity O(n). For very large strings, this could be a limitation. However, for small to moderately-sized strings, this approach is perfectly suitable.