December 26, 2016

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)
}

← A new site | Writing | The Ultimate Guide to Preparing for and Acing CMSC132 →

about

I’m Kevin Chen, and this is my personal website. I am a second-year student in the CS department at the University of Maryland. ¶ My research interests are in machine learning and theoretical computer science. In my free time, I enjoy reading, filmmaking and helping out with Bitcamp.

subscribe

To receive updates from this site, you can subscribe to the  RSS feed of all updates to the site in an RSS feed reader.

search