Well … my brother called me with an odd compiler problem with his C++ homework today (he’s working on another degree, and taking some programming courses) ... but the homework problem he was working on was the infamous N Queens problem:
Given a chess board of N x N squares, place N queens on the board in such a way than none threatens the others. In chess, a queen can move diagonally or horizontally, so solving this requires placing each queen on her own row and column, and ordered such that none of them are on the same diagonal in either direction.
The problem is solvable using a backtracking recursive algorithm: the program must place a queen on the first row and then find a spot that works for the next row, and continue for each row. If it can’t find a spot for a row, it backtracks to the previous row and uses the next legal spot on that row, and if there is none, it backtracks to the previous row, and so on.
Anyway. There’s lots of information about this stuff out there on the ‘net, including dozens of slides shows and lecture notes from dozens of schools, so I’m just going to move on to the fun part: my solution in PowerShell. I wrote it just to make sure I understood the algorithm correctly, without giving away the C++ answer as much as a quick web search would. In fact, I followed the restrictions my brother’s professor had placed on them to break it up into a specific set of functions…
So, I posted a story about Fibonacci sequences and noticed that the recursion in PowerShell is really rather slow. But I also noticed something interesting — I had expected that recursing using a function would be a little cheaper (and faster) than recursing using the pipeline, and it turns out that it’s not. At all.
I’d love to hear some thoughts on why I got the speed results I got here. At first I thought it was something about type coercion, but as you can see, I tried casting everything to no avail. There’s no difference if I don’t output anything, and in fact, the non-recursive algorithm can trivially output every Fibonacci number in the sequence without affecting it’s time (I actually altered it so it didn’t to keep the output clean).
Obviously I expected the recursive algorithms to be slow and scale badly because of the amount of work involved, but how is it that the pipeline-recursive “filter” outperforms the plain old recursive function (albeit by an infinitesimal fraction)?
P.S.: The numbers in braces with the colon (like [18]: ... ) is my prompt.