- It's Not Cheating, It's Learning!
- CrossGuesser 1.1: Download It Here
Recursion: Crossword Pattern Matching
So many programmers' eyes glaze over when the topic of recursion comes up. Either they were bored to tears when they learned about recursion in school, or they were warned so strongly of its dangers that they won't go near it with a 10-foot printer cable. That's too bad, because not only is recursion a powerful programming technique, it's also one of the most fun and satisfying tools you can use as a programmer! Let's see if we can demystify this subject a bit by looking at recursion as it's used in CrossGuesser.
A recursive function is one that calls itself and satisfies two conditions: (1) It has a termination clause, which tells the function to stop calling itself, and (2) it calls itself in such a manner that it will always eventually reach the termination clause (assuming the argument is legal).
The classic factorial example taught in school does not lead to better programming for three reasons: (1) It will run slower than the traditional approach; (2) it will take up much more stack space and could even cause the stack to overflow for large arguments; and (3) a negative number as an argument would cause infinite recursion, so the stack will blow up. The third problem could be solved with an argument check (or perhaps even an unsigned parameter declaration), but even so, a recursive solution is probably not called for.
So when do we want to use recursion? It doesn't run faster than traditional code, but recursion is often much easier to program, especially for very complex tasks. If we don't care about the performance penalty, and the termination condition will come quickly enough that we don't have to worry about the stack, then we should consider using a recursive solution.
CrossGuesser uses a recursive function to match patterns consisting of letters, spaces, and asterisks against each word in the word list. This is done in the function CMainWindow::match which can be found in CrossGuesser.cpp. CrossGuesser's recursive match function is somewhat complicated, because it must mark wildcard (space and asterisk) matches for later color changes, so Figure 3 shows a stripped-down version of match for illustration.
How does this recursive function work? If the first character of the pattern does not match the beginning of the word, it returns false. Otherwise, it calls itself recursively to compare the rest of the pattern with the rest of the word. If a nonmatch is found, it returns false. If the function reaches the end of the pattern and the word at the same time, it returns true. Because the function moves to the next character in the pattern at every recursive call, it will always reach the end of the pattern and terminate. All that remains is to define what it means for the first character of the pattern to match the beginning of the word.
If the pattern is empty (*p is '\0'), we've hit a termination condition. The match succeeds if the word is also empty (*w is '\0'); otherwise it fails. If the first character is a space (*p is ' '), any nonempty word character is a match, so we recurse by moving to the next character of the pattern and the word (match (p+1, w+1) ). In the default case (anything except asterisk) we return false if the first character of the word is different; otherwise, we again recurse and compare the rest of the pattern with the rest of the word.
Matching an asterisk is a bit more complex. First , we move past the asterisk and check to see if we're at the end of the pattern (*++p == '\0'). If so, the match succeeds, because an asterisk at the end of a pattern will match whatever is left in the word. Otherwise, we attempt to match the remainder of the pattern with every remaining position in the word ( for (; *w; w++) if match(p, w) return true; ). We return true for a match at any position, false if no position matches.
The default case is when the pattern begins with a letter. We return false if the first character of the word is different; otherwise we again recurse and compare the rest of the pattern with the rest of the word.
As you can see, there are a few termination clauses and a few different types of recursion in this function. They are, however, all expressed in a concise, elegant way, and the function operates quickly enough for our needs. There is no danger of infinite recursion, because every recursive call brings us one character closer to the pattern's end. Nor are we using a tremendous amount of stack space, because we never recurse more than one level (each nested function call is a level) for each symbol in the word that's being matched. All in all, it's a perfect use for recursion and a function worth studying if you want to add to your bag of programming tools.