What's a good recursion question to ask a prospective employee?

Question

I like to touch on recursion during interviews and am looking for some new ideas. My desired format is to ask the candidate to implement something without any restrictions. Then if he doesn't do it recursively, ask him if it can be done.

Currently, I have Fibonacci and factorial which are a bit too standard for my liking. Recent graduates especially have no problem with these seeing how they are such common teaching examples.

So what are some other good algorithms that I could expect someone to implement recursively in ten minutes or less?

---

Edit: Some good ideas so far are traversing tree structures and solving the Tower of Hanoi.

I'll add that another approach I use sometimes is to give a sample like Euclid's GCD algorithm and ask them what it does. But that can take too long for people to work out and doesn't always offer the same insight.

Answer 1

Walking a tree. It's not really hard but most students don't memorize it, so if they can write it, there's a good chance that they "got" recursion.

Answer 2

I am not fond of generic algorithm questions (e.g., "write a merge sort"). They'll only filter out people who didn't learn the textbook or practiced from an interview book.

Instead, look in your own project and find something recursive and simplify it and ask it as an algorithms questions. For example, you may have some tree form to traverse such as an expression tree, a syntax tree, a call hierarchy, etc.

I think these questions are much more informative, as you will see how a developer thinks in terms that are relevant to you and that require some ability to apply known techniques.

Answer 3

You could have them implement a depth first binary tree search.

Answer 4

Compute the power set of a set.

Answer 5

Ask, "What's a good recursion question to ask prospective employees?"

Answer 6

Build an n level nested xml / html document from an object model something like:

public class Menu
{   
    public string Title;
    public List<Menu> Items;
}

<menu title='File'>
  <items>
    <menu title='Open'/>
    <menu title='Options'>
       <items>
          <menu title='Edit'/>
       </items>

     /menu>
   </items>
</menu>

Answer 7

The Tower of Hanoi problem is easily solved with recursion, and awkward to do without.

Edit: I think the best approach here is to take a problem that is easier to solve with recursion than iteration, and so see if the candidate turns to the recursive solution or the iterative one. I think that would be more valuable than seeing if the candidate can come up with a recursive solution when asked for one.

Answer 8

You can't miss: The Tower of Hanoi!

Since David posted it almost simultaneously, I'll add some more: A recursive descent parser given a simple calculator.

Answer 9

You could ask them to print out all of the files (or only certain file types) and directories in a very large directory structure with many different levels.

Answer 10

Quicksort. Or more specificaly partitioning.

I'm curious, why do you like to ask about recursion, is this a good indicator or dev skills or problem solving? And when you say:

Then if he doesn't do it recursively, ask him if it can be done.

... I think it is harder, and generally more relevant, to ask the other way around. I.e. can you solve a problem that is easy with recursion without recursion.

Answer 11

A very simple to grasp example is comparing two strings byte by byte. Can be done both procedurally and recursively. Return -1 is string 1 comes after string 2 alphabetically, 0 if they are the same, and 1 if string 1 comes before string 2 alphabetically.

Answer 12

The Puyo Puyo and Same Game clearing algorithms are interesting.

Answer 13

Ask them to implement the Fibonacci sequence. If they choose an iterative approach, ask them for the recursive one as well. This also gives you a chance to talk about Big-O analysis.

Answer 14

Define a minimal language that supports recursion, but not iterative loops, goto, etc. and then give them a problem to solve with that language.

Answer 15

Ask the candidate to implement an algorithm for finding the best next move in a simple game like tic-tac-toe or reversi. You could even suggest him to use alpha-beta pruning or to limit the search depth.

Answer 16

I'd vote for picking something less common than Towers of Hanoi. When I had my first interview out of college in 1990, the engineer pointed me at a white board and asked me to write ToH and I answer with disdain, "recursive or non-recursive". It's that easy.

Hermite polynomials are a fairly good one to pick since it is a double recursive relationship.

H0 = 1
H1 = 2 * x
Hn+1(x) = 2 * x * Hn(x) - 2 * n * Hn-1(x)

(from here)

I had this as a CS101 assignment in Pascal, written as recursive, non-recursive, and iterative. I might still have my assignment book at home. If I do, I'll post the assignment.

EDIT - as promised - here's the text from the original assignment:

In this assignment you will write three programs that compute Hermite polynomials. The nth Hermite polynomial is x is denoted by H(x, n), where n is a non-negative integer and x is a real number. The Hermite polynomials satisfy the following recursive definition:

H(x, 0) = 1 H(x, 1) = 2 * x H(x, n) = 2 * x * H(x, n-1) - 2 * (n - 1) * H(x, n - 2) for n > 1

Each program should contain a function H that computes the value of H(x, n). The programs should all prompt the user to enter values for x and n, and print out H(x, n) until he or she enters a negative value for n.

The first program, Herm1, should implement H as a recursive function (this is very easy). The second program, Herm2, should not use recursion but should use a stack to implement the recursive style of the first program. Notice that the computation of H is like that of Fibonacci; that is the number of recursive calls (or pushes on the stack) grows exponentially with n. For the third program, Herm3, you are to implement H with a loop that is traversed at most n times to compute H(x, n). Note: you may not assume any upper bound on n.

This assignment is worth 25 points.

Were I to ask this question, I'd probably ask for any implementation and then start in on questions about complexity and see if the candidate can get to this problem creating a stack issue on their own, and then start down the road of "and how would you solve that?"

Answer 17

Are they likely going to need to implement a recursion alogirthm in the type of code they are going to do for you? If so, ask one related to what they are likely going to have to do..if they are not going to need it in the job you are hiring for, why ask the question in the first place?

Stuff like this can be looked up in 5 minutes in google, someone that can spit it out on demand doesn't necessarily make a good programmer, and someone that needs to take 5 minutes to look it up isn't necessarily a bad one....

I am not a fan of these "lets see how smart you are" questions. Ask them to describe problems they had to solve in there last job, and how they did it.

Answer 18

In one interview I was asked to write an integer to string function. The quickest solution I came up with in the interview used recursion.

Answer 19

Compare two binary trees both in terms of their structure and actual content. If they don't leap to using recursion or at the VERY VERY least use a stack to trace where they have been then you know they never knew about recursion to begin with.

Answer 20

I like to ask these simple questions.

Write a recursive function, foo(n) to print the numbers n through 1. Then change the function so it prints 1 through n instead.