I’ve been doing a lot of interviewing recently. Although we have been getting a lot of candidates through the door, their calibre has been mixed.
I like to ask about recursion during the technical part of interviews. Although it is a basic topic that most people learn about in their first college-level programming course, there are many developers who can’t really describe the concept or any applications of it.
What is it?
Since I’ll be talking about it, I’ll define it:
recursion: defining a function in terms of itself
Some applications of recursion include: any processing which involves tree-like structures, problems which are easier to reason about as smaller versions of themselves.
I don’t expect applicants to give me my definition. Any related definitions or possible applications would also be excellent answers. I like answers that are open for discussion. Discussion is the best way to figure out if someone really knows what they are talking about.
There has been disagreement among my colleagues about whether it’s fair to ask about recursion. Frankly, I can see how a programmer could go through his career without needing to use it. This is how we get interfaces which arbitrarily limit the display or creation of hierarchies to some constant depth. These are the same programmers who when asked about recursion will say it is a form of iteration and leave it at that.
Application versus Concept
The thing that interests me about the lack of knowledge about something so basic as recursion is that programmers who can’t explain the concept have very little hope of describing an application. I don’t believe this is true of most other basic concepts such as Polymorphism, Decoupling, and Generics, for example. There is a better chance of someone knowing the applications of these concepts than being able to define them.
Perhaps this suggests that recursion is an incredibly fundamental, basic concept, rather than one that is complex and advanced.