Tackling Recursion

Posted on Nov 30, 2014

I’ve often read on Stack Overflow and other programming places that solving problems with recursion creates more readable code at the usually acceptable cost of a slightly higher overhead for processing.

While I think that it is more of a personal preference in terms of readability, learning how to think recursively is a valuable skill for a programmer. In this post, we will look at how to approach the idea of recursion by breaking it into smaller pieces using a subroutine and a depth-first decision tree.

Smaller Pieces

One of the biggest benefits to adopting a recursive strategy is that it forces you to break down the problem into smaller problems, rather than trying to solve the entire problem at once. To do that, we are going to talk about one type of recursive pattern, which involves a subroutine. This means that we define a recursive function within our function that we want to repeat until a certain criteria is met.

This is how the basic subroutine outline looks in semi-pseudocode:

Rock, Paper, Scissors

Let’s put this in context. We want to determine the total number of possibilities of combinations that a single player could throw for three games of rock, paper, scissors. We will return our results as an array of arrays, so we expect to receive something like this:

If you have not dealt with these kind of problems before, this may seem like an easy problem. Just loop through all the options and … wait, what happens when you need to start a game with paper? Now it just got a little more complicated. We want to make sure we get every combination without repeating any.

Decision Trees

These type of iteration problems are helpful to think about in terms of decision trees. A good way to think about a decision tree is to imagine that each node on the tree represents a self contained world, where it forgets what came before it and doesn’t care what comes after it beyond its immediate decision.

To put that in terms of our rock, paper, scissors problem, we want to create a decision tree that has every possible combination in it. Then we need to figure out a way to get all those combinations in the arrangement we want them.

Here is an example of how we want to attack the rock, paper, scissors problem (R, P, S for rock, paper, scissors).

rock paper scissors

We start at the top with our initial rock selection. Each node in the tree represents one run of the recursive subroutine as we make our way down the decision tree. Layer two represents the second recursive subroutine. The third layer represents the third recursive subroutine, and the first time we have hit a full game based on our three rounds. The greyed out nodes are currently inactive, but we will get to them soon enough.

The 1 below the R represents the first complete game with “rock, rock, rock”. The 2 below the P represents the second complete game with “rock, rock, paper”.

When we get to the third complete game with “rock, rock, scissors”, we have an issue. We have reached the depth of the current branch, but have other branches to explore. You might be tempted to start from the top again, but that poses a number of problems.

I propose that we only go up one level and move on to the second branch, which is paper. We do that simply by using return to exit out of the current subroutine.

Return to the Rescue

If you haven’t realized it at this point, we actually have three functions in our call stack right now. So returning from the third one will allow the second function to continue executing. That will take us back up to the second level, at which point our loop will continue its iteration and proceed from rock to paper.

Then we call the subroutine again and we are presented with this, where we are presented with results 4, 5, and 6.

rock paper scissors 2

Once we proceed to collect results 7, 8, and 9 from the third branches (scissors), we allow the subroutine to return back to the top node. A that point, we have arrived back at the original call stack, and the loop will iterate from rock to paper for the root node.

Start Coding

First let’s put that into some pseudo code:

Real Codez

Below is my code implementation, along with comments. I have changed the implementation to take any number of user specified rounds, rather than our current limitation of three.

Comments Removed

Here is the code in compact form with comments removed for improved readability

Three Round Results

With a round count of three, here is what the above code produces.

Submit a Comment

Your email address will not be published. Required fields are marked *