Suppose you write a simple program to play a number guessing game: “I’m thinking of a whole number between X and Y…” where the user attempts to guess the number in order to win. Failures that require feedback to the user come in three main flavors:
- The user guessed incorrectly
- The user’s guess was out of range
- The user did something silly, like enter a non-integer value
The do..while form
You can do this with a loop, of course. A do..while loop seems like a natural choice here. What I don’t like is the validation and user feedback in the while clause. You’d call out to a method that hides all of the validation logic, and returns true or false. This is OK, but that boolean method will have a side effect, i.e. feedback to the user.
do { //increment guess count //ask for input //read in input } while ( //input is wrong );
The recursive form
An alternative implementation might use recursion:
static void elicitGuess() { //increment guess count //ask for input //read in the input //validate input inline //Failure: //display relevant feedback //elicitGuess() //else return }
I find this second way to be more natural and readable. But it also feels like the wrong thing to do, though I can’t articulate why. Maybe it’s because any time I’ve seen code that followed this kind of pattern, I’ve seen it written using loops.
Thoughts?
In many languages, the second form does not use constant memory. In the extreme case, you’ll run out of memory. Some languages (like erlang) support tail recursion, which doesn’t have this problem. It can get away with that because it never has to return to the calling function.
Exploding the stack would definitely be an engineering concern, and I actually wrote both implementations because I had time. (Probably the first and last time that will happen this semester.)
I disassembled the bytecode of the recursive version afterward to see if I could tell if it was a goto or something that was obviously recursive, but I quickly discovered the limits of my knowedge when it comes to reading Java ASTs. (A topic that is surprisingly hard to Google for.)
It didn’t appear that it was pushing another frame onto the stack, but it wasn’t obviously a goto, either. As it’s a procedure (the return value is never used), I suspect it might not be endangering the stack.
It did give me an opportunity to dive into tail recursion and tail call optimization, though. Who knew such a simple assignment could be so fruitful. :)
What I turned in used recursion. I don’t think it feels wrong, although I did consider the memory issue and decided that I didn’t care because it’s just homework. Granted, I spent all my tangent time writing a buffer reader from scratch so, that may also have contributed.