Understanding recursive definitions of a language. I am having difficulty understanding the recursive definition of a language.  The problem asked how to write this non recursively.  But I want to understand just how a recursive definition of a language works.
Recursive definition of a subset of L of $\{a,b\}^*$.
Basis : $a\in L$ 
Recursive Definition : for any $x\in L$, $ax$ and $xb$ are in $L$.
Below is my attempt at explaining the recursive definition.
Starting with the basis $a$ saying that $ax$ is in it means that all strings formed such as $\{a,aa,aaa,...\}$ are present.
Defining all $xb$ represents $\{ab,abb,abbbb,...\}$
The answer I have so far is $\{a\}^*\{b\}^*$ but again it is understanding it that I am after.
 A: Pretend you're a computer.
Step 0. You start with $\{ a \}$.
Apply the recursive definitions to each word you have so far. This gives you $aa$ and $ab$, so add them to your list.
Step 1. You now have $\{ a, aa, ab \}$.
Applying the recursion again to each word gives you $aa,ab,aaa,aab,aab,abb$. There's some duplication going on here, but that doesn't matter.
Step 2. You now have $\{ a, aa, ab, aaa, aab, abb \}$.
Do it again. This gives you
$$aa,ab,aaa,aab,aab,abb,aaaa,aaab,aaab,aabb,aabb,abbb$$
so append these to your list, ignoring duplicates as before.
Step 3. You now have $\{ a,aa,ab,aaa,aab,abb,aaaa,aaab,aabb,abbb \}$.
Do you see a pattern emerging? Try and guess the general form of a word in this language and then prove by induction on the 'step' above (a.k.a. structural induction) that your guess is correct.
A:                    a
           /               \
         aa                 ab
    /        \           /       \
  aaa       aab        aab       abb
 /   \     /   \      /  \      /   \
aaaa aaab aaab aabb aaab aabb aabb abbb

A: The recursive definition says that once you have a word of $L$, you can prefix an $a$ or suffix a $b$ to get another word of $L$. You can repeat either of these operations any number of times, so you can prefix $a^n$ for any $n\ge 0$ or suffix $b^n$ for any $n\ge 0$, or both (not necessarily with the same $n$). If you start with the one given word $a$, and apply the ‘prefix $a$’ operation $m$ times and the ‘suffix $b$’ operation $n$ times, you get $a^{m+1}b^n$. (The order in which you perform the $m+n$ operations pretty clearly doesn’t matter.) Since the definition doesn’t allow you to do anything else, these are the only words that you can form:
$$L=\{a^{m+1}b^n:m,n\ge 0\}\;.$$
In other words, you can have any positive number of $a$’s followed by any non-negative number of $b$’s. A regular expression describing this language is $aa^*b^*$; the first $a$ ensures that you get at least one $a$. (An extended regular expression equivalent to this is $a^+b^*$, if you’ve been introduced to the notation $a^+$; it’s just an abbreviation for $aa^*$.)
