This post originated from an RSS feed registered with Ruby Buzz
by Jim Weirich.
Original Post: Kata Two Worked (continued) -- Recursive Binary Chop
Feed Title: { | one, step, back | }
Feed URL: http://onestepback.org/index.cgi/synopsis.rss
Feed Description: Jim Weirich's Blog on Software Development, Ruby, and whatever else sparks his interest.
This is a continuation of the KataTwoVariation1
posting where we are trying different methods of implementing a binary
search. In the first version we discussed an iterative approach and using
loop invariants. In this second installment we cover the the
recursive versions. (see Kata Two
for background information)
Variation #2: Recursive
This is a standard recursive implementation of the algorithm we looked at
in KataTwoVariation1.
This version determines which half of the array contains our target value
and recurses on the appropriate half of the array.
Code
Here’s the code …
def chop_recursive(target, list, offset=0)
if list.size <= 1
(list[0] == target) ? offset : -1
end
mid = list.size/2
if list[mid] > target
chop_recursive(target, list[0...mid], offset)
else
chop_recursive(target, list[mid..-1], offset+mid)
end
end
class TestChopRecursive < Test::Unit::TestCase
alias chop chop_recursive
include ChopTests
end
Problems Encountered
In writing this version, I encountered the following issues …
I had a problem where I miscalculated the array fragment to recurse on. The
miscalculation led to a recursive call where the size of the array
wasn’t decreased, and led to infinite recursion.
Since a copy of the array is passed, we lose information on the position of
the target value in the full array. I had to pass in the offset of the of
start of the array fragment to correct for this.
I refactored the method to return nil (instead of -1) when the target value
was not found. I decided that it didn’t help improve the logic in any
way, so I put the -1 return value back in.
There was a performance bug where I searched both branches of the array
(and then returned the one that matched).
The size==1 test really bugs me. I made several (unsuccessful)
attempts to get rid if it. (But see the next item)
The original version of the recursive version started with …
def chop_recursive(target, list, offset=0)
return -1 if list.empty?
return offset if list[0] == target
return -1 if list.size == 1
...
This version tests list[0] agains target at the entry to
every recursive call. This is wrong. I should only test when the list is
down to one element. This defect made it into the original posting and it
wasn’t until I was reviewing the code for the CPS post that I
discovered the error. It also might explain my discomfort with the
list.size==1 test. It was actually the list.empty? test
that was incorrect and the size check evolved to list.size <=
1.
Variation #3: Recursive with Explicit Limits
In variation 2, I decided to pass a copy of the sub-array in each recursive
call. This is an expensive operation, but I was thinking that I could avoid
passing around explicit limits this way. However, it turned out that I
still needed to pass the offset, negating much of the advantage.
In variation 3 we will avoid makeing array copies by always passing the
original array around. Instead of arrays, we will explicitly pass the hi/lo
limits of the sub-array in the recursive call.
I think this version is not only more efficient than variation 2, it is
also easier to read and understand.
Notice that the recursive call in this version takes 4 parameters, so I
created a helper function (rchoplim) with the proper signature to
do the recursion.
Code
Here’s the code …
def chop_recursive_passing_limits(target, list)
rchoplim(target, list, 0, list.size)
end
def rchoplim(target, list, lo, hi)
if (hi-lo) <= 1
list[lo] == target ? lo : -1
else
mid = (lo+hi) / 2
if list[mid] > target
rchoplim(target, list, lo, mid)
else
rchoplim(target, list, mid, hi)
end
end
end
class TestChopRecursiveWithLimits < Test::Unit::TestCase
alias chop chop_recursive_passing_limits
include ChopTests
end
Problems Encountered
There were no problems encountered while implementing Variation 3. I think
the simpler logic helped (plus I worked out a number of bugs in Variation
2).
Things to Come
In the next installment, we will explore a CPS (Continuation Passing Style)
implementation.