Recursion Practice Interview Problems?

[kmiklas]

Hey All,

What are some good practice problems for recursion?

My current list is:

- Factorial of a number. This is everywhere; from Stroustrup to Stackoverflow to my old Calc book. It seems to be the quintessential question on recursion.
- Traverse a binary tree
- Quicksort (KnR 1988 pg. 87)
- Towers of Hanoi
- Calculate the nth fibonacci number
- Generally speaking, stack work.

Any others that stand out in your mind?

Thx Keith :^)

[helios]

Factorial and Fibonacci aren't good recursion examples, because they're trivially and more efficiently written as iterative functions.

* Sudoku solver
* Labyrinth solver

Bonus points: rewrite the algorithm to avoid recursive calls. Note that you may need to manually maintain recursive state in stack-like data structures.

[kmiklas]

Factorial and Fibonacci aren't good recursion examples, because they're trivially and more efficiently written as iterative functions.

Perhaps in a production setting, but in the context of an interview, either is perfect as a quick check for understanding of the concept.

Stroustrup 2013, pg 309 gives:

int fac(int n)
{
    return(n>1) ? n*fac(n-1) : 1;
}

Questions like this can catch you by surprise. Under pressure, if you haven't seen it in a while, combined with "interview nerves," it could catch you off-guard.

If a candidate can't provide this (or something close) in less than 5 minutes, it says a lot.

[helios]

In a production setting, there's plenty of arbitrary precision factorial implementations that are ridiculously fast. Additionally, Fibonacci has a closed form O(1) (unless you're working in arbitrary precision) expression for the nth element.

If someone is caught off-guard by a recursive factorial function then they're a total fraud, I agree.