Chad Perrin: SOB

30 April 2008

recursion confessional

Filed under: Geek,Profession — Tags: , , — apotheon @ 11:45

I have taken a couple of college classes in programming. I remember conversations after class with the instructor from my Programming 101 (not sure that’s what it was actually called) course, where we strayed from C/C++ (the implementation language(s) for the class) to matters related to Cobol and Perl, among other things. I remember being frustrated by the fact that while taking a class in JavaScript, I discovered that I learned programming more slowly in a formal education environment than on my own.

Otherwise, my programming learning has basically all been self-taught. As a result of this, I tend to learn the stuff for which I have a real use, and that’s about it. Oh, sure, I “learn” some stuff for purposes of wanting to know how things work as an academic exercise, out of curiosity and fascination, but if I don’t have real-world applications for what I’m “learning” I don’t really learn it in a way that makes it ultimately useful when the real-world application of the concept does rear its head. It’s only then that I actually learn it in a practical, applicable manner.

I got to thinking about this in part because I reread Dan Kegel’s How To Get Hired — What CS Students Need to Know. In it, he identifies three basic programming skills that many programming job applicants (surprisingly) lack:

  1. looping (e.g. “Write a loop that counts from 1 to 10.”)

  2. doing basic arithmetic in your head (e.g. “What’s the number after F in hexadecimal?”)

  3. practical recursion (e.g. “Use recursion to solve a real problem.”)

The reason this got me thinking about my (lack of) “formal” education in programming is point three — practical recursion. See, I’ve never really had to use recursion in the real world, and it sure didn’t come up in introductory courses in C, C++, and JavaScript. The obvious use-case for recursion is parsing arbitrary depth hierarchical trees, such as directory structures — but the vast majority of my “real world” work has been in Perl, PHP, and Ruby, all of which make implementing the actual tree-parsing algorithm an exceedingly rare necessity for common cases. In such languages, the recursion is done for you. Ruby compounds the “problem” by providing such excellent iterators that even in the rare case, you can put together an easier, more elegant-looking solution with an iterator block than with recursion anyway (and punishes deep recursion by failing at tail-call optimization, too, at least as recently as version 1.8).

Of course, the first time I had a real-world problem to solve where recursion was the obvious best choice, I’d surely learn it sufficiently to solve that little deficiency in my skillset, but this still offers two problems:

  1. Being unfamiliar with recursion outside of gratuitous examples like Fibonacci sequence generators, I may well not notice when a recursive solution is marginally better than the iterative solution I’m using instead. It would take a really obvious (to me) need for recursion for me to notice I needed it, I suspect.

  2. The ability to learn concepts quickly and apply them well while learning them doesn’t prepare me for the circumstance posited in Dan Kegel’s essay: job interviews. In other words, he probably wouldn’t hire me.

Every once in a while, I find myself kicking around the idea of getting hired on at a “normal” programming job. One of the things that holds me back (aside from all the other things, like my enjoyment of rolling out of bed at 10:30 instead of jumping up at 6 AM, choosing the projects I work on rather than toeing a corporate line, et cetera) is the fact that any place I’d want to work, in an environment with smart programmers doing interesting things, I’d probably lack some of the “signifier” skills interviewers would expect of me. The very best places would be those where someone would think to ask “Why don’t you know how to do this?” rather than just chalking up my ignorance to incompetence — thus perhaps allowing me the chance to get in anyway — but that’s such a rare case that I’m unlikely to find a hiring dev shop like that anyway. It’s difficult enough finding a place that doesn’t have arbitrary, pointless requirements like “must have Master’s degree” for “entry-level programmer” jobs.

I’m probably a prime example of what people who value certain levels of “higher education” in “computer science” (note that the quotes around CompSci are meant to denigrate the quality of most CS degree programs, not the concept of CS itself) like to use as examples of how right they are to ignore matters like intelligence, passion, adaptability, integrity, and other actually useful characteristics, preferring sheepskin as the Metric Most High for a new hire. This isn’t because I’d be bad at the job, even if it required constant use of advanced recursive techniques. It might take me a month to spool up to the same speed on recursion as everyone else there, sure — but the initial investment would be worth getting me rather than someone with a Master’s in CompSci who’s dumb, plodding, rigid, and prone to doing everything for CYA value rather than the success of the project.

None of that changes the fact that, without the standard CS degree program course of study, I’m at a distinct disadvantage for certain types of interview skills-test questions.

At least I know that the next number after F is ten, though.

20 Comments

  1. I learned to love recursion back in my Algol days, and when I changed jobs in 1983 I was disappointed to learn that DIBOL (the language used by my new employer) did not allow recursion. I labored under that restriction for about ten years until Synergex added recursion to Synergy/DE version 5 (which I helped with). Now I’d have a hard time going back to the days without it.

    As I mentioned in our chat earlier, you can think of recursion as a loop with a stack for the local data. In fact, in languages without support for recursion, you can mimic it by using a stack and a loop. You emulate a nested call by pushing the local data on a stack and loop. When that iteration is done, pop the data off the stack and proceed. For complex cases you might have to stack more than the data (e.g., some representation of what operation you were in the middle of performing).

    As you mentioned, parsing is one of the best use cases for recursion. For instance, parsing an expression like “(x + (5 – i))” could benefit from a recursive routine to process a simple parenthesized expression. When nested parentheses are encountered, recurse.

    Comment by SterlingCamden — 30 April 2008 @ 12:22

  2. Here’s an essay that I think sorts out the issues of academic vs. self-taught programmers:

    http://www.lambdassociates.org/Blog/hackers.htm

    Basically, learning stuff from a good academic CS program (either via material posted online or by going to lecture) stretches your mind. Curriculums are designed to introduce you to things that you wouldn’t normally run across hacking on your own, and recursion is a good example. Once you know recursion, you have another tool in your toolbox for solving problems in the best way. There’s also a lot of pedagogical nonsense that you have to cut through in a standard CS curriculum, but they’re built on nuggets of wisdom that can make you a better hacker. By no means does that imply that CS graduates know anything about programming, but they had the opportunity to pick up some great skills that are hard to acquire without years of experience and learning from their mistakes.

    Comment by Reid — 30 April 2008 @ 12:50

  3. > looping (e.g. “Write a loop that counts from 1 to 10.”)

    Why not answer question 1 and 3 at the same time?

    // javascript function range(first, last) { …if (first >= last) …{ ……return []; …} …else …{ ……var rest = range(first+1, last); ……return cons(first, rest); …} }

    function cons(item, list) { …var newlist = [item]; …for (var i = 0; i < list.length; i++) …{ ……newlist.push(list[i]); …} …return new_list; }

    (Cons really works better with linked lists, but Javascript doesn’t have those built in).

    Comment by Tac-Tics — 30 April 2008 @ 12:56

  4. Some of the “canonical” Python code for directory traversal uses recursion. See shutil; here is a version I use. Comment lines removed because your blog does really weird things when I use the Python “#” character at the start of a comment. “pre” tags also don’t seem to work… sorry about the formatting. I also can’t claim to write very “Pythonish” idiomatic Python.

    def backupfiles( sourcepath, destpath ): names = filter( filtersvn, os.listdir( sourcepath ) ) os.mkdir( destpath ) for name in names: newsourcepath = os.path.join( sourcepath, name ) newdestpath = os.path.join( destpath, name ) try: if os.path.isdir( newsourcepath ): backupfiles( newsourcepath, newdestpath ) else: copy2( newsourcepath, newdestpath ) except ( IOError, os.error ), why: print “Failure copying file %s to %s: %s” % \ ( newsourcepath, newdest_path , str( why ) ) return

    Here’s a little routine to dump out a list of parameters from a dict, handing punctuation.

    def oneParameterAsStr( paramdict ): return ‘%s %s’ % ( paramdict[‘type’][‘type’], param_dict[‘name’] )

    def parameterListAsStr( paramlist ): if len( paramlist ) == 1: # handle each parameter return oneParameterAsStr( paramlist[0] ) else: # recurse on the list, adding ‘, ‘ when we have more parameters return ‘%s, %s’ % ( oneParameterAsStr( paramlist[0] ), parameterListAsStr( param_list[1:] ) )

    voidt def allParametersAsStr( paramlist ): if [] == paramlist: return ‘ voidt ‘; else: # wrap the list with spaces return ‘ %s ‘ % ( parameterListAsStr( param_list ) )

    In general I’ve learned to avoid using recursion much in C/C++, because it gets awkward, but a lot of algorithms in Python are a lot clearer expressed recursively, so if you know you have a small finite data set, and it’s for a non-performance critical bit of code, why not use it?

    In Haskell, recursion is practically an art form:

    qsort [] = [] qsort (x:xs) = qsort (filter (= x) xs)

    The use of pattern matching and recursion means that algorithms that are ugly in other languages become ultra-clear. You have to go out of your way to avoid expressing things like this recursively in Haskell, and laziness + tail call optimization makes them pretty efficient, too.

    Comment by Paul R. Potts — 30 April 2008 @ 12:56

  5. Recursion is a very regular way to deal with arbitrary amounts of very regular things. Don’t just think in terms of recursive code – data structures can be recursive. A linked list is an empty list or its a value (the head) linked to a linked list (the tail). A binary tree is either an empty tree or a node with left and right binary tree children.

    Once you see things that way, code just falls out the same way. Transforming an empty linked list means returning an empty linked list. Transforming a non empty list means transforming the head value and linking that as the head for the transformation of the tail. Visiting an empty binary tree means to do nothing. Visiting a non empty binary tree means visiting the left child tree, visiting the head, then visiting the right child tree.

    Whatever language you use has some recursion in its definition. In a c-ish language for instance: an expression is a block, or a variable declaration, or a variable assignment, or an if chunk, or… A block is an open curly brace followed by a series of expressions followed by a close curly brace. An if chunk starts with if and a predicate in parens then has an expression then maybe has an else and an expression. Etc.

    Comment by James Iry — 30 April 2008 @ 01:02

  6. Reid:

    Basically, learning stuff from a good academic CS program (either via material posted online or by going to lecture) stretches your mind. Curriculums are designed to introduce you to things that you wouldn’t normally run across hacking on your own, and recursion is a good example.

    I wouldn’t argue against that, per se. It’s entirely possible to learn this stuff without attending a class, of course — or without even checking online course materials. There are books galore both online and off that cover such material. The only problem I’ve found as a self-taught programmer is the opportunity to put it into practice.

    As Sterling pointed out in his own comment, even that isn’t really a necessary problem of autodidactic programming instruction — he’s a self-taught programmer that has used recursion a lot. I just haven’t worked under the same conditions. I’m looking for opportunities to use recursion so that I’ll “get” it more fully, in a practical, useful sense (without trying to shoehorn everything into a recursive solution), but I suspect I won’t have much need for it for a year or so.

    By no means does that imply that CS graduates know anything about programming, but they had the opportunity to pick up some great skills that are hard to acquire without years of experience and learning from their mistakes.

    This is one of the reasons I wish I’d had an easier opportunity to get a good CS degree. I started pursuing such a beast, but found that the degree program sucked — so I switched majors and figured I’d get back to it later at some point. So far, I haven’t.

    Tac-Tics:

    Of course, if they actually wanted you to loop from 1 to 10, a recursive solution wouldn’t be appropriate. On the other hand, if they’d accept a recursive solution to the looping question, you’re dead-on. In fact, if I thought a recursive solution was the easier approach for me, I’d take it first — and see if they wanted me to redo it as an iterative loop instead (or maybe also do it as an iterative loop, on my own).

    Paul R. Potts:

    Comment lines removed because your blog does really weird things when I use the Python “#” character at the start of a comment.

    SOB uses Markdown syntax for formatting. In Markdown syntax, # is used to indicate an h1 heading, and ## to indicate an h2 heading, et cetera. You can escape Markdown’s special characters with backslashes.

    “pre” tags also don’t seem to work

    There are, for some reason, some issues with the way WordPress handles code formatting. You might try <pre><code> to see if that works for you. You might also try inserting an extra four spaces at the beginning of every line of code, which is the Markdown syntax for pre/code formatting of a block of text. In-line code formatting in Markdown uses backticks to “quote” the code (like I did for <pre><code>, so that it looks like `\<pre>\<code>` when I type it out).

    Hopefully I got all the character escaping right, here.

    James Iry:

    Once you see things that way, code just falls out the same way.

    . . . assuming some familiarity with recursive implementations in practical use, I think. I think pretty recursively about a lot of things, but my programming experience leads me to think otherwise — such that, even when looking at recursively structured data, I find myself thinking iteratively in terms of how to work with it. It’s a habit I’ll have to break when I do finally get around to doing things where recursion would be more appropriate.

    In General:

    Thanks to all for giving me more to think about on the subject. I am interested in plugging this hole in my experience, and I guess the “recursion confessional” was something of a veiled cry for help.

    Comment by apotheon — 30 April 2008 @ 01:21

  7. > I’m looking for opportunities to use recursion so that I’ll “get” it more fully, in a practical, useful sense.

    Come up with a project where the data set is either language-like or hierarchical: – A parser for a programming language – A calculator that can evaluate things like (3 + (5 * 7)) – A file utility that will calculate the size of a directory – A GUI system that supports nested controls – A tool to convert XML to a tightly packed binary format

    Comment by bob — 30 April 2008 @ 01:37

  8. Come up with a project where the data set is either language-like or hierarchical:

    I’m looking for such opportunities that are things I actually have the interest and need to pursue (or can come up with reasonable excuses for saying I have the need). Many of the things you suggest are already “solved problems” within the sphere of work I can justify pursuing at this point, though. For instance, I already have the du utility at my beck and call, and any calculator I wrote would be a step backwards from the plethora of tools I have at my fingertips.

    Programming language parsers should be fun, of course, but there are other things I need to learn before I start on that.

    Thanks for the suggestions, though. I’ll keep them in mind for special-case opportunities that might arise.

    Comment by apotheon — 30 April 2008 @ 01:46

  9. There’s of course a lot of wonderful applications of recursion in AI. Backtracking, A*, logic solver(i.e. Prolog) – all fun to implement. If you’re into graphics, kd-Trees and Octrees are nice examples. Or write a simple ray tracer. If you’re into math, there’s the standard example of GCD, or you can do Mandelbrodt(sp?) rendering. Logic puzzles? 8 queens and travelling rooks.

    If you really want to dig into the fundamentals, I suggest working with lisp – the whole car/cdr thing almost forces recursion on you. (Yes, functional languages will do, too)

    That should keep you busy for a bit of time ;)

    If that’s still not enough, I suggest getting a copy of Etudes for Programmers and working through the examples. That should give you quite a bit of exposure to recursion and other useful CS techniques.

    Comment by Robert 'Groby' Blum — 30 April 2008 @ 07:31

  10. Logic puzzles? 8 queens and travelling rooks.

    I might tackle those.

    If you really want to dig into the fundamentals, I suggest working with lisp – the whole car/cdr thing almost forces recursion on you. (Yes, functional languages will do, too)

    I’m actually planning on getting into OCaml at some point in the not-too-distant future. I’ve toyed with it a touch in the past, and it seemed like it could be fun. Lisp is a little further into the future for me, though I’ve very briefly toyed with that as well in the past.

    If that’s still not enough, I suggest getting a copy of Etudes for Programmers and working through the examples. That should give you quite a bit of exposure to recursion and other useful CS techniques.

    Nice recommendation. Thanks.

    Comment by apotheon — 30 April 2008 @ 09:58

  11. My interview questions have always been very language specific (“what’s an abstract class in C#”; “show me an example of a self-join in T-SQL”, etc.), so I’ve never demonstrated any basic skills such as looping or recursion. I think in the former case interviewers just assume that a candidate must know looping constructs since they’re so common, and in the latter it never occurs to them to ask. It seems like it’s just one of those techniques that is nice to know, but you only pull it out of the box to solve very specific types of programming problems.

    As far as education goes, I’m largely self-taught too, and so far my lack of a formal background hasn’t hindered me much; back when I was taking CS courses, we used C++ as the teaching language, which I have never used in a professional capacity. And in my experience interview questions have rarely been language-agnostic. (When they have been, they’ve generally been about object-oriented programming.) So depending on the type of job you might be interested in, I wouldn’t worry about a lack of a formal education–once you get to a certain level in your career, your experience and industry knowledge tends to trump the book-learnin’ stuff.

    And no, you don’t really want a “normal” programming job. ;-)

    Comment by Brian Martinez — 1 May 2008 @ 12:04

  12. […] Chad Perrin: SOB » recursion confessional We all have our deficiencies, but this one suprised me. (tags: recursion programming apotheon) […]

    Pingback by links for 2008-05-01 -- Chip’s Quips — 1 May 2008 @ 01:39

  13. And no, you don’t really want a “normal” programming job. ;-)

    I guess I should have phrased that differently. You’re probably right about not wanting a “normal” programming job.

    Comment by apotheon — 1 May 2008 @ 09:52

  14. Recursion, regardless of which language you use to express it, is a technique for expressing solutions to problems that yield better to being solved recursively than other types of problems.

    What do I mean by this?

    Off the top of my head, implementing quicksort comes to mind – there are both, well-known, recursive and non-recursive (iterative) implementations of this very well-known algorithm.

    However, if you look closer at both implementations, even though the iterative one isn’t expressed with calls to self, it uses a stack to carry out the same behavior that the recursive implementation does without using a stack – because the LIFO (stack) behavior is provided to you in the recursive implementation by virtue of function calls to self (with a proper terminating/sentinel condition, obviously, or else you’ll blow the stack there too).

    There might be other ways of expressing quicksort which are beyond recursive or iterative w/stacks, but I am not aware of them – nor do I much care to be, because the recursive one does the job quite admirably & simply.

    On the other hand, printing a C-based ASCII, null-terminated, character string can be implemented very easily with 2 lines of recursive C code, or 2 lines of iterative code – and this is where a whole lot of heated debate opens up, with “problems” such as these – where you have people who are ardent functional language supporters on one side of the fence, mudslinging at the other (iterative) camp, and expounding on the virtues of recursive vs iterative solutions to a simple and stupid problem like printing a C-based null terminated string.

    The functional people will tell you that the functional approach leaves no room for side-effects that are experienced w/iterative/imperative languages, but when you poke under the surface of such statements, you realize they hold ground until you have to invoke a system call (e.g. write() to some UNIX FD – a socket, pipe, port, console, whatever…) to do something useful, at which point a side-effect will be introduced between two such identical function calls (in our case, print a C-based, null-terminated, string), in the sense that they both are competing for the same resource, and synchronization is implied, or else you get race conditions/garbled output….

    The iterative/imperative people will tell you that that you should not use anything but a ‘for’ loop to print a string, along with a local variable (or a char* pointer until you hit null) to index through the string, while calling putchar()…. and that using recursion to express a solution to this type of problem is stupid… and then the imperative/iterative people will take it a step further and say recursion is probably stupid on all counts :) (ok, I’m exaggarating here to make a point), until they have to actually attack a problem like quicksort or one of many other problems (which I have no room to go into, but check out Siskena’s Algorithm Design Manual book on AMZN for samples), at which point, they start to love recursion because once they understand its divinity, expressing the solutions become quite simple, of course….

    Should you understand recursion, or more importantly, recognize its applicability to a given problem, when going into an interview? Certainly. You might not be able to implement it in a span of 45 minutes, but I never much cared that people implement anything precisely when I interview them so long as they are able to recognize the domain of problems that yield to being solved better recursively than iteratively (or vice versa, as was the example with printing a C-based string).

    Definite answer? There isn’t one – and you should know both techniques and use them accordingly. If you stick to a definite answer, you become a zealot, and you run the risk of pissing people off just by mere virtue of wanting to be right about the tool you are using, whether it’s recursion or not….. and when you’ve got only a hammer at your disposal, then all problems tend to look like nails. That is precisely the predicament you are attempting to avoid when you are a programmer, that most immature, young programmers fail at avoiding and thusly piss others off – or worse, work themselves into blindly believing that one paradigm of thinking is “better” or “more” than another one, typically unfamiliar to them…..

    Or as my CS professors used to say, you will ALWAYS, in CS, trade time for space, or vice versa…. It’s much the same philosophy with algorithmic techniques – you are trading one approach’s benefits for another, while achieving the same goal- but just be aware of that…… and that’s probably enough to pull you through anywhere as a programmer. Silver bullets do not exist.

    Comment by Martin N. — 1 May 2008 @ 04:29

  15. Thanks for the thoughtful response. That pretty much mirrors my beliefs about the subject — including the notion that I really need to get more comfortable with recursion for “real-world” problems. My favorite part of your comment was this:

    Should you understand recursion, or more importantly, recognize its applicability to a given problem, when going into an interview? Certainly. You might not be able to implement it in a span of 45 minutes, but I never much cared that people implement anything precisely when I interview them so long as they are able to recognize the domain of problems that yield to being solved better recursively than iteratively (or vice versa, as was the example with printing a C-based string).

    ’nuff said

    Comment by apotheon — 1 May 2008 @ 04:36

  16. My apologies, the author’s name of the “Algorithm Design Manual” book is Steve Skiena – I misspelled his last name. It’s a great hands on book and it dives rather deep into the types of problems you will see in the “real world” (e.g. your job, my job, a job at Google, MSFT, AMZN, etc.)…. To get cozy w/recursion, start w/simpler stuff, like computing Fibonacci sequences, GCD, binary search, factorial, Ackermann, string permutation, etc. Then do more complex things like write a recursive-descent parser (e.g. for arithmetic expression evaluation to begin with, or a LISP parser perhaps).

    Once you get the hang of it that a recursive solution breaks down (divide ‘n’ conquer) a problem in identical subproblems, and you get thru the hardest part of how to set up the function in such a way that you reach a finite solution to some problem, you will train yourself to “think recursive”…

    But above all – start with a problem. Don’t start with thinking about recursion, or “wanting to get better at recursion” – that’s a pitfall. Recursion is a tool, a way to express a solution to something on turing complete machines… So start with a problem, then work out how you will solve it (recursively, or not).

    Comment by Martin N. — 1 May 2008 @ 04:58

  17. Martin N., do you have a blog? I’d subscribe.

    Comment by SterlingCamden — 1 May 2008 @ 05:14

  18. Nah.. even if I did, I’d be restating what Spolsky, Graham, Yegge, Schwartz, Skrenta, Atwood, Sink, et al – keep pounding onto everyone else who is less mature/experienced in the virtues of computer science (and software engineering, which is how a majority of CS grads are manifested on their resumes, rather than “computer scientists” – which would probably require a Ph.D. in the matter to bestow yourself such noble, freewheelin titles ;) – you either LOVE this job and you’re good at it, consistently employed and doing a job you love – or – you SUCK, don’t enjoy it, are barely making ends meet and your job chooses you rather than the other way around ….

    Those that LOVE CS & programming, tend to resemble the above people & their computing/programming philosophies … and there’s many people who don’t have blogs that are exactly of the same caliber as our more outspoken counterparts….. (e.g. I know Yegge from AMZN, where I used to work… and I’ve also met Gavin King personally too, while at AMZN).

    What’s funny is, it doesn’t take long to recognize people like these… in an interview or in real life. I’ve never really had a problem getting any hardcore programming job in the last 12 years… but then again, computing has been an infatuation of mine since I was 8 years old.. (I’m 32 now…).

    BTW, I only have a web page – http://www.naskovski.info… no blog yet. Thanks for the kind words.

    Comment by Martin N. — 1 May 2008 @ 06:46

  19. […] [From Chad Perrin: SOB » recursion confessional] […]

    Pingback by Mediocre programmer confessional — 2 May 2008 @ 08:19

  20. […] April 2008, under the title recursion confessional, I discussed the fact that my mastery of the Force recursion was less than complete (to put it […]

    Pingback by Chad Perrin: SOB » If I Was Better — 23 August 2009 @ 08:21

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