# Constructing a recursive definition.

I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of numerical expressions, but with strings it starts to get a little confusing for me.

The problem I have is this: Construct a recursive definition for $f(x) = xy$, where $y$ is the reverse of $x$ for strings over the alphabet $\{ a, b \}$.

I guess I start getting confused when it says y is the reverse of x.

So what I am thinking is that we have this:

$f(\Lambda) = \Lambda$, $f(xa) = af(x)$, $f(xb) = bf(x)$.

But them I am confused on where $y$ goes. Any ideas on what I am doing wrong?

First of all, let me recall the definition of the reverse. If $x = a_1a_2 \dotsm a_n$, then the reverse of $x$ is the word $\tilde x = a_n \cdots a_2a_1$. Note that I am using the notation $\tilde x$ instead of $y$ to remember that it depends on $x$. You will see why this is important below.
Thus, by definition $f(x) = x\tilde x$. If $1$ denotes the empty word, we have $f(1) = 1$. Next, you tried to compute $f(xa)$, where $a$ is a letter, but you made a mistake. In fact, $f(xa) = xa\widetilde{xa} = xaa\tilde x$, which does not help much to get a recursive definition.
Let's try instead to compute $f(ax)$. Then we get $f(ax) = ax\widetilde{ax} = ax\tilde xa = af(x)a$, which gives the required recursive definition. Let us compute for instance $f(abb)$ to check whether our recursive definition works. We get successively $$f(abb) = af(bb)a = abf(b)ba = abbf(1)bba = abb1bba = abbbba = abb\widetilde{abb}$$ It looks good!