Coding up a recursive solution to a problem you’ve never seen before might seem tricky, but there’s a step-by-step process you can follow to figure out exactly when and how to code recursive solutions.

First, when?

You can use recursion in any problem where the answer can be obtained in an easy way, assuming you know the answer to a simpler problem.

For example, if you want to calculate the weight of the 50th floor of the empire state building, and you know that each floor is half as heavy as the one below it, then you could use recursion to calculate the 50th floor based on the 49th floor (which is based on the 48th … and so on), until you reach the base floor– whose weight you would need to know.

Note: If anyone is familiar with inductive reasoning (see CMSC250), the process of recursion is virtually identical.

Secondly, how?

Lots of students get frustrated mistakenly trying to think through a recursive algorithm the whole way through (e.g. through all 50 floors in the previous example), but that’s not the correct approach to construct a recursive solution. Instead, try this:

  1. Write down the simple base case
  2. Pretend that you know the answer to the case(s) that are slightly simpler than the answer
  3. Calculate the answer from the answer to the slightly simpler case(s)

Let’s try this with the canonical university example: calculating the fibonacci number for a number n.

  1. We know that the fibonacci number for 0 is 0, and 1 is 1.
  2. We pretend we know the answer to n - 1 and n - 2
  3. We now can easily calculate the fibonacci number n, by adding the fibonacci of n - 1 and n - 2.

The recursive solution is then as follows:

int fib(n) {
  if n == 0:
    return 0
  if n == 1:
    return 1:
  return fib(n-1) + fib(n-2)