The definitions given in the previous section don’t really make it any easier to see how recursion works, or why we should even invest our time in it. It may seem like this concept is far removed from the bulk of computing, however, it is integral to almost all the programs we write today. As computer scientists, engineers, or enthusiasts, it turns out that recursion plays a huge role in all the programming we do.

     How? One word: compilers. You may be familiar with compilers as the program that translates your java or c++ or other code into a form that is more easily understood by the computer. What you may not have known is that when a compiler checks your code to see if it is valid syntax of your particular language, it uses recursion. A language is usually defined with something called a grammar, and this grammar can often be recusively defined.

     The entire scope of this topic is very complex, and beyond this tutorial, but I’ll relate the general concepts and how the relate to recursion. Basically, the language grammar is defined like this:

Definition 6.) Java Language Grammar:
The grammar for a language such as java defines the rules that proper program code must follow in order to be valid. This requires rules for valid java tokens, and rules for their interaction. The rules for interaction are simply rules of syntax.

Wow, that definition of a language grammar is pretty simple, right? Sure doesn’t seem to have gotten us anywhere, I mean, what is a valid java token? Therein lies the trick.

Definition 7.) Java Token:
Tokens are identifiers, keywords, literals, seperators, and operators of the java language, or a set of these tokens interacting in a valid manner, as defined by the language grammar's requirements.

So a valid java token is defined as a set of valid java statements and tokens as defined by the grammar? Seems a little circular. That sure doesn’t seem to have gotten us anywhere either.

     The magic in a definition like this if you define a valid java document as a set of valid java tokens separated by semicolons (lines of code), and you define the valid java tokens as sets of other valid java tokens (variable names, declarations, method calls, if statements), which can also be in turn be made up of more valid statements, etc, you can quickly create a way for a computer to check the syntax of a program without requiring human intelligence and understanding.

     If you tried to write a parser or compiler that worked with code without breaking up the code into smaller and more manageable general blocks, the problem would be impossibly complex for today's programming languages. To do this recursively, all you have to do is define the two things required for a recursive definition: the base case and the rule from getting from a simple case to a more manageable one. The base case for a valid token: a single token that fits the java definition above for a valid token. And the rule for defining a more complex valid java statement would be: other valid tokens and a set of syntactical rules to separate the ‘valid java tokens’.

     For a more concrete way to show this, let’s use what we’ve learned to define a fake language. And how are we going to define it? Well, with a recursive definition, of course!! Therefore, we’ll need a base-case and rules for defining a set (or sentence/statement) of our language in terms of smaller valid sets separated with proper syntax.

     Let’s say that this language that we’re making is made entirely of words composed of the letters a and b, separated by spaces or commas. We can check any general string to see if it is a valid example of this language (we’ll call it language foo). The recursive definition would be as follows: first we have the base case, a valid statement (single word in this case) in foo is any number of a’s and any number of b’s, in any order. Now, we can define a valid statement in foo as any number of valid statements in foo separated by spaces or commas. So, the string "aa ab,aababa,abb a" would be a valid foo statement, while "a. bn" would not.

     So, hopefully by now, we’re convinced that recursion at least can be useful, but next, we’ll take a look at how recursion works in detail.