Here is my second post, a week after the first. As said before, it is about recursion in computer science.

Recursion (in Computer Science)

My first post was about using recursion to solve math problems. However, recursion is also a common method to solve programming problems. I will try to present everything in a way that is not language-specific, and I will also post code in Python and Java (the languages I am most familiar with). For Java, I will simply post the function, to run the code paste it into your own class, and call it in main.

There is one large difference between recursion in math and programming. In math, using a recursion to find a larger value works forwards, and the values calculated are increasing. In programming, a recursion works backwards.

Recursion is used in computer science to break down problems into smaller cases of the same problem. This is achieved by having a function call itself, which seems counter-intuitive at first, but turns out to be very powerful.

Recursion requires two parts:

1. A base case

2. A recursive call

The base case is a conditional statement that checks whether the recursion has reached a value that is already known. The base case is very important! Without a base case, the recursion will never end, and the program will not finish (usually resulting in a stack overflow).

The recursive call is at least one call to the same function, and is required for you to actually be implementing recursion.

This may seem confusing at first, but let us apply recursion to a simple problem.

Given a positive integer $n$, find $n!$ using recursion.

The motivation to apply recursion is that there is a simple relationship between factorials of consecutive integers: $n!=n(n-1)!$ So, let us try this. To use recursion, we write a function $factorial$ taking one input, $n$, that calculates factorials. It simply returns $n\times factorial(n-1)$.

Python:

def factorial(n):
    return n*factorial(n-1)

Java:

static int factorial(int n) {
    return n*factorial(n-1);
}

Run the above code in your own environment, with an input of, say, $5$. Does the function return $120$, as it should? No, it doesn't. In Python, an error message says

RuntimeError: maximum recursion depth exceeded

and Java throws a

java.lang.StackOverflowError

What happened? You might notice a missing piece of the function. The recursive call is in the function, but what about the base case? Try tracing how the function runs.

Here is what the function ends up returning after 5 calls: $5\times 4\times 3\times 2\times factorial(1)$ This seems fine. Continuing, $5\times 4\times 3\times 2\times 1\times 0\times -1\times -2\times -3\times factorial(-4)$ Uhhh, not looking so good anymore. In fact, this never stops, and this is why the maximum recursion depth is exceeded and the stack overflows.

Hopefully, that illustrated the horrors of forgetting the base case. Now, let us try to add the base case. What value of $n$ is the smallest possible, the one that doesn't rely on other values? Since $n$ is a positive integer, $n=1$ is the base case. If the input is $1$, what should the function return? Simply $1!=1$. All this takes is a single if-statement.

Python:

def factorial(n):
    if n==1:
        return 1
    return n*factorial(n-1)

Java:

static int factorial(int n) {
    if (n==1) return 1;
    return n*factorial(n-1);
}

Try running these functions in your own environment with an input of $5$. They should both return the correct value, $5!=120$.

Okay, problem solved, on to the next problem:

A board is composed of a row of 10 squares. A token starts on the leftmost square, and has 15 moves. Each move, it can stay still or move 1 square left or right. If the token cannot move off the board, in how many ways can the token end on the 10th square after all moves are used?

To use recursion on this problem, we try to split the problem into smaller and smaller problems, until the problem becomes something like

1. In how many ways can a token on square $x$ end on the 10th square with 0 moves left?

The answer to this, is, of course, 1 if $x=10$ and 0 otherwise.

The initial problem can be split into these three problems:

1. In how many ways can a token on square $1$ end on the 10th square with 14 moves left?

2. In how many ways can a token on square $0$ end on the 10th square with 14 moves left?

3. In how many ways can a token on square $2$ end on the 10th square with 14 moves left?

Now, notice that every possible problem can be split into three parts, one to the left with one less move, one in the same square with one less move, and one to the right with one less move. This motivates creating a function that takes two parameters. We want parameters that uniquely define the problem. Think for a little about what the two parameters should be...

Okay, got it? If not, here is the answer. We want one parameter that tells us how many moves are left. We want a second parameter that tells us which square the token is on. Adding the total number of squares is also a possibility, but it is the same for every one so this is not necessary.

Now, let us write this function. First, try to write it on your own. Remember, the function should take two parameters, and it should have a base case, and a recursive call. The base case is when the problem shouldn't be split anymore: if the token fell off the board, there are 0 ways, and if there are 0 moves left, the answer is determinable. The recursive call should return the sum of all possible positions with one less move. Take a few minutes to try to write the function.

Python:

def token(moves, square):
    if moves==0:
        if square==10:
            return 1
        return 0
    if square<1 or square>10:
        return 0
    return token(moves-1,square-1)+token(moves-1,square)+token(moves-1,square+1)

Java:

static int token(int moves, int square) {
    if (moves==0) {
        if (square==10) return 1;
        return 0;
    }
    if (square<1 || square>10) return 0;
    return token(moves-1,square-1)+token(moves-1,square)+token(moves-1,square+1);
}

Both of these functions return the correct answer, $\boxed{23115}$.

Problems:

1. Write a recursive program to compute the triangular numbers (the sum of the numbers from 1 to $n$).

2. Here

3. Write a recursive program that makes a certain number of cents into coins (pennies, nickels, dimes, and quarters).

4. Here

Congratulations on making it this far, and thanks for reading! Please tell me if this was too hard, easy, confusing, or anything like that.

Next week we will talk about recurrence relations, and the week after, probably more on recursion in computer science!