Long ago, a friend offered a challenge to help me learn. An aspiring developer himself, he'd taken several programming tests at job interviews. He forwarded one of them to me. The goals were as follows:
- Goals:
- generate a grid of random characters
- display the grid to the screen
- read in a dictionary file (more a word list, really)
- iterate through the list, obeying a set of rules to search the grid for each word
- Rules: using recursion:
- when seeking the next letter in a word, navigate only one spot at a time
- navigate only in the cardinal directions (up, down, left, right)
- never use the character at a single grid location more than once on a given attempt
- once a given word is discovered, don't search for more instances of it
- display the number of words discovered
- complete in 8 hours, 6 hours for bonus points
The first time I attempted this, years ago, it took me about a week's worth of evenings, totalling about 16 hours or so of total time. That's too long, and in the real world I would have failed that programmer test miserably. But it did give me an opportunity to learn about recursion.
I still need to sit down and plan out my recursive algorithms if I want them to be clean and efficient, but at least I have a firm grasp of the concept. This time around, I was able to solve the problem in under 5 hours. Here is how I tackled the task:
First thing being first, I generated a grid of chars using a two dimensional array to satisfy Goal #1, and slapped together a simple print function to cover Goal #2. Later, instead of simple characters, I came up with structs that contained both a char and a bool (for checking whether a given char had been used during any given check attempt). Then I had to (I admit) Google a way to read in a word list from a text file. Incidentally, Goals #3 and #4 were achieved with the same single while loop, but that part of the solution isn't relevant to the topic of recursion. (You can still see how I did it by viewing the project on my GitHub page, linked at the bottom of this post.)
It was finally time to sort through the grid to see if a given word was contained within it ... using recursion! First, how does recursion work? Recursion is a way of looping that's a little more confusing and involved than a simple for or while loop. These types of loops generally (if clearly and cleanly constructed) encapsulated chunks of code that run over and over again until a condition is met, then they stop looping and the program moves forward. Recursion, likewise, allows you to loop a chunk of code over and over again until a condition (usually called the "base case") is met. However, instead of a simple keyword call such as for or while, a recursive function is called. That is, a function that runs some code, and then calls itself, resulting in a looping effect.
- A recursive function runs some code and then calls itself to create a looping effect similar to a for or while loop.
- A recursive function iterates by receiving values from previous calls to itself as arguments, then checks those values to see if the "base case" has been met.
- (In some cases, a recursive function may modify and check a variable that is outside its scope and check that variable for the "base case".)
- When the "base case" is met, the ultimate result of the nested recursive function calls is returned down through the chain (or "stack") of calls to the original.
Take the following C++ snipped as an example. Notice how this simple function:
- accepts a value to get it started
- checks if the value has met the goal (or "base case") - modifies the value and passes it to another call of itself
- returns the result back down the chain
Here is a quick walkthrough of how this simple recursive function performs its duties on a call with the value 8 passed to it.
- First, recursiveExample( 8 ) is called. CompSci professors would describe this as placing a call to recursiveExample on the "call stack." In simpler terms, we're on the first layer of recursion and our value is currently 8.
- recursiveExample checks if the base case has been met; but value is less than 10.
- Since the base case was not met, we go to the else block. Here, value is incremented by 1, and recursiveExample calls itself, passing value (currently 9) as the argument.
- Now there are two instances of recursiveExample on the call stack; we are on the second layer of recursion.
- recursiveExample checks if value (currently 9) meets the base case, but it doesn't, so again we go to the else block.
- In the else block, value is iterated once more, now to 10 (can you predict what will happen next?). recursiveExample then calls itself again, passing value (currently 10) to itself as an argument.
- We now have three instances of recursiveExample on the call stack, and we're on the third level of recursion, and we have received 10 as the value for our value variable.
- recursiveExample checks the base case, and sees that it is met (value is greater or equal to 10)!
- Since the base case was met, recursiveExample returns value, which is 10. This removes one instance of recursiveExample from the call stack and returns us down to the previous call of recursiveExample.
- We are now back down on the second layer of recursion. Recall that the last thing we did on this layer was to call an instance of , the second layer of recursiveExample. We pick upu exactly where we left off, and the next thing to appear in code is another return! So that's exactly what we do; return the 10 on down the chain. The 10 is returned, and this second instance of recusiveExample is removed from the call stack.
- At last, we are back down at the bottom layer, to our original function call. Again, we pick up where we left off and the next piece of code is another return. So we pass the 10 on down, and since this is the final layer of recursion, the 10 is what ends up actually being returned to the program that originally called recursiveExample in the first place!
I used this idea of recursion in my word search program in checking the grid for successive letters of a given word. For example, taking the word "banana," I would search the grid for a 'b', then pass the word "banana" into my recursive function along with an iterator to represent the position of the next letter in "banana" that I was searching for. That function would check for the base case (in this case, if the letter position iterator had been incremented all the way up to the full length of the word I was searched for). If the base case was not met, the function would search the neighboring grid spots for the next letter in the word. If it found that letter, it would call itself, passing an incremented value as the iterator, with a reference to "banana" (or whatever word). This would continue until an instance of the letter-searching function met the base case (in which case it would return true all the way down the chain), or the function was unable to find the next letter while obeying all the rules of the WordSearch challenge (in which case it would return false all the way down the chain). Here, you can see what this recursive function looks like in my program:
You can see my WordSearch program in its entirety on my GitHub page! The recursive function itself is called checkNextLetter, and it can be found on line 76 of main.cpp, here. It's a bit more complicated than the simple example above, but you can spot some of the basic elements of a recursive function. For example, see lines 79 to 82, where checkNextLetter checks if the base case has been met and returns true if it has. Also check out lines 88, 95, 102, and 109 where checkNextLetter calls itself (and increments the spot value at the same time), creating the recursive equivalent of the looping effect.
Thanks for reading!
--
Steven Kitzes
