Discrete Math Recursive Functions for Strings

Question

Recursive Functions for Strings

Construct a recursive definition for the following string function over the alphabet {x,y}:

f(x) returns the string where every x is replaced by xy and every y is replaced by yx.

Answer 1

A good way to deal recursively with strings is to separate them into a first element and a tail, and to deal with each separately. So, for example, "hello there" is 'h' followed by "ello there". What you'll typically then do is suppose that you already have f("ello there") and work out how you might construct f("hello there") from that. Almost all the work is already done – how do you finish the job?

For example, if you were trying to reverse "hello there", and you had that "ello there" reversed is "ereht olle", all you need to do is stick the "h" on the end to get "ereht olleh", which is the answer you were looking for.

Of course, it's just as permissible to split the string on the last element, or somewhere in between. The important point is that when defining $f$ you may use $f$, but only on shorter strings, so that you know you won't get a circular definition.

(Actually, there are other ways to avoid circularity, but this is a simple one that is sufficient for your purposes).