To understand recursion, you must first understand recursion…
Google “recursion” and the top result will be “Did you mean: recursion”
In college one of my professors had stated that recursion is a method for making the computer do most of the work for you. Its a way to reduce a a complex algorthm to a few lines with a base case.
But object-oriented recursion is a bit different;
object-oriented recursion represents the invocations themselves as objects, sending the same message to different objects
Procedural recursion is coded as a function that calls itself with different parameters until a base case is met.
Let’s have a quick review of procedural recursion using a purposely verbose factorial function;
1 2 3 4 5 6 7 8 9 10
Okay, so we need to know the factorial of 3. We have written the above function and now we’ll execute it with the number three. The execution would look something like this (the verbosity will make sense)
#factorial(3) 3 != 1 recursiveCallResult = (factorial(3 - 1)) result = null #factorial(2) 2 != 1 recursiveCallResult = (factorial(2-1)) result = null #factorial(1) 1 == 1 recursiveCallResult = null result = 1
The base case of the function is met and the operation begins to “unwind” back up to the original call;
#factorial(2) recursiveCallResult = 1 result = 2 * 1 result = 2 #factorial(3) recursiveCallResult = 2 result = 3 * 2 reusult = 6
As it turns out, the factorial of 3 is 6!! Cool!
Object-Oriented Recursion is a way to make the objects do all the work!!
Kent Beck’s article on Object-Oriented Recursion was an epiphany to me when I first read it in 1996. It opened my eyes to different ways of working with objects. It made even more clear to me the concept of polymorphism. To be able to send the same message to different objects is a powerful concept.
I have used the Peano Number example from the article when teaching myself a new programming language as it helps me to understand how polymorphism can be applied in that language. Also the example is just plain fun. If interested, the translations are available for Ruby, C#, and Dart.
Mancala & OO Recursion
One of the classes that we created for the Mancala game kata was the Well. A Mancala ‘well’ holds a number of seeds and is owned by a player. On a players turn, the player will take all the seeds from a selected well, then “sow” a single seed to each well starting on the well to the right till all the seeds picked up from the initial well have been “sown”, then the next player takes their turn.
The ‘Well’ class for the Mancala game presented an excellent opportunity to demonstrate an object-oriented recursion solution. Especially since there is also a GoalWell which is handled a bit differently when the seeds are sown. A player can only place a seed in a goal well when the player owns that goal well.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Each well knows about the well to its right, its next_well, so the data structure is a circular linked list.
1 2 3 4 5 6
Each well can be assigned a number of seeds;
well01.seeds = 2
When gameplay begins, a player will select a well and will “sow” from that well;
The sow method is the starting method for the operation.
1 2 3 4 5
1) In this method, the current number of the seeds is held in a temporary variable “current_seeds”;
current_seeds = self.seeds
2) The seeds instVar is set to 0;
self.seeds = 0
3) Lastly, the well’s next_well is requested to take_seed sending the current_seeds and starting well’s owner for the parameters. This line of code
self.next_well.take_seed(current_seeds, self.owner) begins the object-oriented recursive operation,
Lets have a closer look at the
1 2 3 4 5 6 7
1) One is added to this well’s seed count;
self.seeds += 1.
2) The count that is passed in is reduced by 1;
count = count - 1
if count > 0 tests for the base case. If count is not greater than zero, then the base case is met and the operation will not continue.
3) If count is greater than zero, then the next_well is called to `take_seed’
Lets now look at the Mancala Goal Well. According to the rules a player can only place seeds in his own goal well.
Lets create a subclass of Well to handle this special case for take_seed.
1 2 3 4 5 6 7 8 9
When a GoalWell is sent the message take_seed, it must first check if the player is the same as the owner. If it is, then it will call its super class’ implementation of the take_seed method.
If the GoalWell’s owner is not the same as the player, then the GoalWell call’s its next_well to take_seed. The distribution of the starting well’s seeds continues till the base case of no more seeds (a count of zero) is reached. Then the next player can select a well and sow.
Okay, we’ve described the code, lets look at what the “sow” execution would look like.
Let’s create some wells and do a step by step description of the execution.
well01 = Well.new(:player1) player1GoalWell = GoalWell.new(:player1) well02 = Well.new(:player2) player2GoalWell = GoalWell.new(:player2)`
Now lets link our wells up together;
well01.next_well = player1GoalWell player1GoalWell.next_well = well02 well02.next_well = player2GoalWell player2GoalWell.next_well = well01
We’ll place 3 seeds in well01,
well01.seeds = 3. The other wells seeds are initalized to 0. Play will begin with with well01 invoking “sow”.
#well01.sow ------instVars well01 ----- well owner is player1 self.seeds is 3 next_well is player1GoalWell ------------------------------ current_seeds is 3 self.seeds is set to 0 next_well(count=3, player=:player1)
player1GoalWell is the next_well and belongs to player1. Also player1GoalWell is a GoalWell class.
#player1GoalWell.take_seed(count = 3, player = :player1) ------instVars for player1GoalWell ----- owner is :player1 self.seeds is 0 next_well is well02 --------------------------------- :player1 does equal self.owner <:player1> so we call the super take_seed implementation on the Well class self.seeds = 1 = 0 + 1 count is 2 = 3 -1 count is GREATER than 0 and the base case has NOT been met, execution continues next_well(count=2, player=:player1)
well02 is the next_well and belongs to :player2. It is a Well class.
#well02.take_seed(count = 2, player = :player1) ------instVars for well02 ----- owner is :player2 self.seeds is 0 next_well is player2GoalWell --------------------------------- self.seeds = 1 = 0 + 1 count is 1 = 2 -1 count is GREATER than 0 and the base case has NOT been met, execution continues next_well(count=1, player=:player1)
The next_well is player2GoalWell. It belongs to :player2, so it will do something a bit different;
#player2GoalWell.take_seed(count = 1, player = :player1) ------instVars for player1GoalWell ----- owner is :player2 self.seeds is 0 next_well is well02 --------------------------------- :player1 does NOT equal self.owner <:player2> so the code calls the next_well take_seed implementation on the Well class next_well(count=1, player=:player1) self.seeds remains 0
The next_well is well01, right back where we started from!
#well01.take_seed(count = 1, player = :player1) ------instVars for well01 ----- owner is :player1 self.seeds is 0 next_well is player1GoalWell --------------------------------- self.seeds = 1 = 0 + 1 count is 0 = 1 - 1 count is NOT greater than 0. The base case has been met so the operation stops here!!
Each of the wells count for seeds should be
well01.seeds is 1 player1GoalWell is 1 well02.seeds is 1 player2GoalWell is 0
This Mancala Well example demonstrates Object-Oriented Recursion with two well types, Well and GoalWell being polymorphic, performing the take_seed operation. Each well delegates to the next well to handle updating their seed count, decrementing from the seeds being sown and testing for the base case to end the sow operation.
Have fun with OO recursion!!
The source for this example can be found at Mancala Well