Recursion, Part Zero

I’ve mentioned recursive programming techniques several times over the years in this blog (Topological Sort, How Not To Teach Recursion, Fibonacci Challenge, Recursion and Dynamic Programming, Sometimes Breadth Is Better Than Depth, and probably a few others).  A lot of developers, particularly those without a formal education in computer science, are still pretty vague on this weird idea of functions that call themselves. 

If you’re interviewing at Microsoft for a development position you can expect that at least one person will ask you a whiteboarding question that involves some kind of recursive problem. This isn’t because we’re a bunch of architecture astronauts or theory wonks, it’s because if you want to be a dev here, recursion is simply one of the tools that you have to have in your toolbox. We use recursive data structures and algorithms quite a bit, and people are expected to know how they work.

I’d therefore like to take this opportunity to do a series on some of the theory and practice of writing recursive and recursive-like functions. I want to show that (a) they’re not as mysterious as they seem, but (b) that they are potentially dangerous, and (c) there are some absolutely crazy-but-fun techniques for turning a recursive program into a nonrecursive program. Hopefully by the time we’re done here your head will hurt, but hey, it builds character.

I’m going to get as much of this done as possible and queued up, because I’m going to go dark shortly. I’m getting married in less than two weeks! Between getting ready for that and finishing up stuff at work, I’m going to be swamped. (And you’d better believe I’m not blogging about recursive programming techniques from my honeymoon.)  I’ll be back in late August and things should pick up then.

Comments (6)

  1. nksingh says:

    Congratulations, and thanks in advance for this series.

  2. Hmm, you mean you’ll have something more interesting to do on your honeymoon than blog about recursive programming techniques? Intriguing!

  3. EricLippert says:

    I mean that I’ll have no access to computers. We hope to spend most of our honeymoon on a cruise ship with a highly trained staff bringing us another glass of mango juice — which is less interesting, but a whole lot more relaxing than, say, work.

  4. Neyah says:

    What? You mean there isn’t a publicly accessible wireless access point for your laptop that goes out through a satellite uplink? For shame!

  5. baljemmett says:

    Now, see, that’s the sort of relaxation I could do with! I was on holiday for a week recently; the boss promised to leave me alone, and until the penultimate day he did. Luckily he only disturbed me to arrange a site visit for the day after my return…

    [I wonder how this form knows my URL on this machine but not in the office? Guess I’ll find out if I’m logged in or something if/when this posts!]