I was recently asked to write a simple algorithm using recursion. I immediately baulked because the algorithm was so trivial and recursion was such a bad choice.
But for novelty sake i wrote it up on the whiteboard. It was wrong, I didn’t put the termination condition in, but I don’t program whiteboards anyway and the fact that the problem was so stupid to solve as recursion had me befuddled.
But it has made me think. Think about how bad the solution I wrote up was. I was asked to write a recursive solution, to a linear single loop problem, so I wrote it thinking like I was solving a problem which was best solved by recursion. Solution ran n^2, I knew it, was the biggest reason why I thought writing the algorithm with recursion was stupid.
Later I was thinking, it wouldn’t be that hard to make the recursion linear, its still a terrible way to solve the problem but at least its still linear.
But it was only just now that the obvious truth hit me, you can turn any loop into a recursion trivially without changing the asymptotic performance (your performance will likely drop, and you’ll probably stack overflow, but the O notation won’t change). I had been so focused on the request for recursion that I didn’t do what I should have done, which is solve the problem the right way, and then make that fit the requirements. (Not that that is a good motto for general development…)