Chad Perrin: SOB

19 September 2010

using recursion to solve a real problem

Filed under: Geek,Profession — apotheon @ 02:55

Back in the days when discussing the FizzBuzz problem of interviewing programmer job candidates, Dan Kegel had this to say:

Speaking on behalf of software engineers who have to interview prospective new hires, I can safely say that we're tired of talking to candidates who can't program their way out of a paper bag. If you can successfully write a loop that goes from 1 to 10 in every language on your resume, can do simple arithmetic without a calculator, and can use recursion to solve a real problem, you're already ahead of the pack!

My question is simple: What counts as "a real problem" one can solve with recursion that would be small enough to be a quick job interview question (like the FizzBuzz question)? I don't seem to run afoul of problems that call for recursion very often. When I do, it seems like it's always a "toy" problem like a Fibonacci number generator or factorial calculator.

I'm pretty sure I could solve a "real problem" using recursion, at that level of complexity at least, if I ever ran across one.

9 Comments

  1. Tree walking... particularly useful for folks working with XML. A reflection-based tree walk might be a good one for an interview too. But those are the only two recursive problems the typical programmer will see in their career.

    J.Ja

    Comment by Justin James — 19 September 2010 @ 03:30

  2. Thanks. I completely forgot about recursive tree parsing — which I've only dealt with explicitly once. The fact that the vast majority of programming I've done has been with Perl, PHP, and Ruby means that XML parsing is a rare thing and walking a filesystem is easily accomplished via built-in functions and/or standard library functions.

    Comment by apotheon — 21 September 2010 @ 11:42

  3. I've used recursion once in my professional career, and in an XSLT function, no less! So yes, definitely useful when parsing XML, but for most programming problems there are usually simpler solutions. I think if a programmer can at least explain what recursion is, they probably know what they're doing.

    Comment by Brian Martinez — 21 September 2010 @ 01:13

  4. I think if a programmer can at least explain what recursion is, they probably know what they're doing.

    That definitely describes me. I can explain all kinds of things I've never used in a "real-world" situation, including several ways to sabotage an automobile engine. I read a lot, y'know.

    I imagine that the majority of professional programmers never use recursion, actually, so you're probably ahead of the averages.

    Comment by apotheon — 21 September 2010 @ 01:32

  5. My favorite example of a nicely recursive "real-world" task is bill-of-materials processing, often encountered in a manufacturing context. The cost of a manufactured assembly is the sum of the cost of component parts plus associated labor. However, the component parts themselves may be manufactured assemblies. (e.g. a hand-held electric drill, made up of motor, chuck, bearings, housing, switch, and cord; motor is made up of frame, stator, rotor, and bearings; rotor is made up of shaft, stampings, wire, etc.) I remember hearing an IT guy from a manufacturing plant describing proudly how they solved it in RPG; they "simply" gave assigned part numbers so that the part number of an assembly was constrained to be greater than the part number of any sub-assemblies, then computed costs in a single, key-ordered sweep of the database. (Hmmmm. I hope their part numbers were assigned sparsely enough to allow for versioning...)

    There are actually many good examples of business processes that can be naturally expressed as recursively walking a hierarchical data structure; given that most organizations draw their org charts as trees, you can probably think of many HR-related examples (tallying salaries within all hierarchies, tallying awards received within all hierarchies, etc.)

    IMHO, the alleged "complexity" (or fragility) of many business programs is directly due to the attempt to solve the problem with non-recursive thinking.

    Comment by Joel Neely — 7 December 2010 @ 06:31

  6. Thanks for the examples, Joel — those are excellent demonstrations of practical use of recursion.

    Comment by apotheon — 7 December 2010 @ 06:39

  7. hi dear,

    The cost of a manufactured assembly is the sum of the cost of component parts plus associated labor. However, the component parts themselves may be manufactured assemblies. (e.g. a hand-held electric drill, made up of motor, chuck, bearings, housing, switch, and cord; motor is made up of frame, stator, rotor, and bearings; rotor is made up of shaft, stampings, wire, etc.) I remember hearing an IT guy from a manufacturing plant describing proudly how they solved it in RPG; they "simply" gave assigned part numbers so that the part number of an assembly was constrained to be greater than the part number of any sub-assemblies, then computed costs in a single, key-ordered sweep of the database

    Comment by phone tracker — 13 January 2011 @ 02:09

  8. Ok, before it gets too weird, let's see an example of a real-life problem, and how we can use recursion to solve it.

    Real Life Example

    Let's assume you have moved to a new apartment. You are exploring the neighborhood, and you suddenly discover that you don't know your house number. You looked at the building, didn't find a number there. You knocked on a random apartment, and asked, "what is the number of this building," and the guy who opened the door smiled and said, "I don't know the number of this building, but if you look at the number of the building next to us and add 1, you will know our building number."

    Now, let's pause for a moment. The problem you are trying to solve is "knowing the number of your house." Let's look at the proposed solution to this problem. What was the suggestion? You were asked to look at the number of the building next to you and add 1. Your problem was thus reduced into a problem of exactly the same nature! At first your problem was "to find the number of a house," and your problem now became "finding the number of a house."

    Comment by executive items — 13 January 2012 @ 06:09

  9. Years later, I have found myself using recursion probably slightly more often than I should, considering that I occasionally find myself rewriting recursive algorithms to use (clumsier) iteration so that I will not end with too deep a stack level.

    I just figured I'd update.

    I'm going to close comments on this, now, because I'm not really maintaining this any longer. My newer devlog is blogstrapping, and you're welcome to check it out.

    Comment by apotheon — 6 April 2012 @ 03:23

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License