We’ve propably all heard that tail recursion is the way to go. That’s true, but as I’ve learned today applying this principle does not free you from thinking about your code.
The task was to implement the
Josephus game. That’s particularly straight forward in imperative languages such as Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
| private int josephus(int amountOfSoldiers, int interval) {
List<Integer> soldiers = new LinkedList<Integer>();
for(int i = 1; i <= amountOfSoldiers; i++) soldiers.add(i);
int index = 1;
while(soldiers.size() != 1) {
for(Iterator<Integer> iter = soldiers.iterator(); iter.hasNext() && iter.next() != null; ) {
if(index++ % 3 == 0) iter.remove();
}
}
return soldiers.get(0);
} |
But Java is not much of a challange, so lets give this a shot in Haskell:
1
2
3
4
5
6
7
8
9
10
11
12
13
| josephus :: [Int] -> Int
josephus [] = 0
josephus [x ] = x
josephus l = josephus _ l 1 where
josephus _ [x ] _ = x
josephus _ xs o = let
len = length xs
off = ((o + len ) ` mod` 3) in
josephus _ (dropByInject o xs ) off
dropByInject _ [] = []
dropByInject m (x:xs ) | m ` mod` 3 == 0 = dropByInject (m + 1) xs
| otherwise = x: (dropByInject (m + 1) xs ) |
Obviously the dropByInject function is not tail recursive. When we call the following program
which computes the “Josephus number” from 1 to 2000 soldiers, takes roughly 0.792s.
So I did a second shot which is tail recursive:
1
2
3
| dropByInject r _ [] = r
dropByInject r m (x:xs ) | m ` mod` 3 == 0 = dropByInjectAp r (m + 1) xs
| otherwise = dropByInjectAp (r ++ [x ]) (m + 1) xs |
. And here is where I stopped thinking – which immediately became clear to me as the same task as above takes 23.791s. Wow, that’s not really better than the 0.792s of the not-tail-recursive version. So why is that:
if we take a look at how the list is constructed in the otherwise part of the dropByInject function we see that the x is appended to the end of the list via
. And that was the mistake – lists in Haskell are linked lists and appending to linked lists takes 
as we have to find the end of the list first. Upps
Alright, let’s go for a third shot:
1
2
3
| dropByInject r _ [] = reverse r
dropByInject r m (x:xs ) | m ` mod` 3 == 0 = dropByInjectTr r (m + 1) xs
| otherwise = dropByInjectTr (x:r ) (m + 1) xs |
This version takes only 0.704s. That’s not lightyears of speed gain compared to the first version, but hey at least it’s tail recursive.
