Programming Interview Questions: Recursion

In this screecast we solve two commonly asked interview questions; faculty and traversing binary trees.

Screencast

What’s recursion?

A recursive function is simply a function that repeatedly calls itself and the trick is to realize when to stop calling ourselves to avoid infinite loops that result in stack overflows.

If the interviewers ask you to write down an algoritm that gives you the n:th fibonacci number, calculate faculty or traverse a binary tree they probably want you to provide both an iterative and recursive solution. We don’t address fibonacci in the screencast, but the formula for the n:th number is simply the sum of the previous two, i.e.

f(n) = f(n-1) + f(n-2)

Is this a good interview question?

Here’s the recursive methods I developed during the screencast to calculate faculty and to sum the value of all the nodes in a binary tree:

    private static int sum(Node node) {
        if (node == null) return 0;
        return node.Value + sum(node.Left) + sum(node.Right);
    }
    
    private static long faculty(int n) {
        if (n == 1) return 1;
        return n * faculty(n - 1);
    }

As you can see the answers are usually very simple but it’s not unusual to see candidates try to make things more complicated than they need to be. Just keep it simple.

Interviewers tend to ask these kind of questions even if functional programming is a very small part of the day to day work. It’s always good to be prepared by training on some simple problems similar to the ones covered here. After one or two exercises you’ll get the hang of it and it won’t be a problem if they throw these kind of questions at you during the interview.

And as always, until next time, have a nice day!