Recursive algorithms for string operations

Question

I am trying to write recursive algorithms for the following string operations:

1) An algorithm to reverse a string.

2) An algorithm to test if two strings are equal to each other.

3) An algorithm to check if a string is a palindrome (for example, "eye" or "racecar") - reads the same forwards and backwards.

I am fairly new to writing algorithms, so even examples of procedures/similar methods would be appreciated.

Answer 1

Induction Steps: In each example, I'll show how to reduce the size of the problem by a little bit. You will need to do the base cases on your own.

• To reverse "abcd", just take the last character "d" and stick it at the beginning of whatever the reverse of "abc" is.

• To check if "abcd" equals "fbcd", just check that the last characters of each word ("d" and "d") match and that the remaining characters ("abc" and "fbc") match.

• To check if "racecar" is a palindrome, just check that the first and last characters ("r" and "r") match and that the middle leftover part ("aceca") is a palindrome.

Answer 2

Imagine we have a function that takes two string parameters, say first and last, and it returns last+first as a string.

function reverseString(first,last) {return last+first;}

So:

reverseString('world','hello')

returns 'helloworld'.

Our string to reverse is say 'abcde', and we expect the result to be 'edcba'.

We might begin with a function call to reverseString, say;

reverseString('a','bcde')

which returns 'bcdea'.

Now it gets technical - to perform a recursive call, we call reverseString() from inside reverseString(). We are going to assume that first is only ever $1$ letter long, and that the original call to reverseString() is of our required structuring.

function reverseString(first,last) {

output=first+output;

while (length(last)>0) reverseString(last[0],last-last[0]);

return output;}

Now there are loads of other computery things to do, such as make sure output is declared and initialized properly, and it has the correct scope, but these are covered elsewhere, for example StackOverflow.

And all the output values are still returned, but unless we 'catch' the value, they are ignored.

So:

reverseString('a','bcde')

sets output='a' and calls:

reverseString('b',cde');

which sets output='b'+'a'='ba' and calls reverseString('c','de');

So we then have:

output='cba'. Call reverseString('d','e');

output='dcba'. Call reverseString('e','');

output='edcba'.

Now last is empty, so the original function call is terminated, and the returned value is 'edcba' as required.

---

To test if two strings are equal is not really recursive. To test for palindromes, reverse a string and see if it equals itself.