Module 2: Recursion

Module Overview

Explore recursive algorithms, their implementation, and when to use them effectively. Understand the power and limitations of recursion in solving complex problems.

Learning Objectives

• Understand the concept of recursion and how it works
• Identify base cases and recursive steps in recursive algorithms
• Implement recursive solutions to common programming problems
• Analyze the time and space complexity of recursive algorithms
• Compare recursive and iterative solutions to the same problem
• Identify the base case for a given recursive algorithm
• Identify the recursive case for a given recursive algorithm
• Analyze the pros and cons of solving a given problem with a recursive vs an iterative solution
• Implement a recursive algorithm given a problem statement
• Convert an iterative algorithm to an equivalent recursive algorithm

Understanding Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller instances of the same problem. For recursion to work properly, it must have:

• Base case(s): Condition(s) that stop the recursion
• Recursive case(s): The function calls itself with a simplified version of the problem

Recursive solutions are often elegant and can clearly represent the problem structure, especially for tasks that have a natural recursive definition, like traversing tree structures or calculating factorial values.

What is recursion?

Recursion means applying a rule repeatedly in order to solve a problem. In software development, a recursive method is one that contains a call to itself in order to perform its function repeatedly, each time on a slightly smaller version of the original problem. In this reading, you'll learn more about what a recursive method is and see some examples of how they work.

Recursive methods always handle two types of cases, the recursive case and the base case. In the base case, the method actually returns. In a recursive case, the recursive method calls itself again, with simpler/smaller input data or problem. It will then use the return from the simpler/smaller problem to perform a simple operation and return its own result. Put another way, the recursive case simplifies the problem that it receives in a small way, deferring the solution of a slightly simpler problem to the same recursive method. Recursion breaks the larger problem down into smaller problems and uses the same simple rule to solve the smaller problems.

Think about a child putting away toys. "Clean your room" is a big problem, but we can break that down into a recursive case and a base case. The recursive case would be to clean up smaller areas in your room, making the task smaller and easier to handle. The base case would be when the area to clean is so small there is only one toy in it. The base case would then have you put that one toy away. This allows us to break a big problem, "Clean your room," into the same small problem over and over again, "put away a toy." Eventually, you will have solved the "Clean your room" problem.

Figure 1. An animation of recursively cleaning your room. Each recursive call to clean your room, makes the room one toy smaller. When there is just one toy in the room we have reached the base case of "put away a toy." "Put away a toy" returns when that toy has been put away. It returns to the room that called the method. That room should now just have one toy. We proceed back up to the full room, cleaning up one toy at a time.

Figure 1. Cleaning your room recursively. Each recursive call to clean your room, makes the room one toy smaller. When there is just one toy in the room we have reached the base case of "put away a toy." "Put away a toy" returns when that toy has been put away. It returns to the room that called the method. That room should now just have one toy. We proceed back up to the full room, cleaning up one toy at a time.

Notice that if our method only implemented recursive cases, it would continue calling itself until filling all the memory allocated for the stack. This error condition is called a stack overflow (which can occur in non-recursive code but is most commonly encountered by recursion gone awry).

In order to avoid stack overflow errors, recursive methods must always include at least one base case. A base case is a condition that can be handled by returning a value without making any further calls to the recursive method.

Sometimes, the base case is the goal of our recursive method. A base case may occur when whatever purpose we wanted our recursive function to achieve is met. A recursive algorithm may have more than one base case, or terminating condition. For the "Clean your room" example, our base case is:

put away a single toy

If we were searching our room recursively to see if we had a particular toy on the floor, we may have two base cases:

• when we find what we are looking for (we return the found object)
• when there is nothing left to search (we indicate that the object is not in the room)

Sometimes, however, the base case isn't the goal itself, but instead the place to start building up the answer to the recursive call. One problem often solved recursively is listing the Fibonacci number sequence, which is a series of numbers beginning with 0 and 1. Each successive number is the sum of the previous two numbers. So 0 and 1 is followed by 1, because 0 + 1 = 1. This gives us: 0, 1, 1. The next number in the sequence is 2, because the two previous numbers are 1 and 1, and 1 + 1 = 2. The sequence now looks like: 0, 1, 1, 2. And we can continue to build the sequence in this way. When we write a method to solve the Fibonacci number sequence, we usually give it a parameter "n", which specifies the length of the sequence we want to return. This length is 0 based. So n = 0, returns "0" and n = 3, returns "0, 1, 1, 2".

This means the two base cases for the Fibonacci sequence are:

• Find 0th Fibonacci number, n == 0 (return 0)
• Find 1st Fibonacci number, n == 1 (return 1)

In this example, we begin with the number of Fibonacci numbers we'd like to list. The Fibonacci function makes recursive calls to itself, each call reducing by one how many Fibonacci numbers to compute, n = n - 1. So if we initially call the Fibonacci method with n = 3, it will recursively call itself with n = 2. The recursive calling continues until we reach a base case, when n == 0 or n == 1. The base cases are not the goal of this recursive method, but instead the starting point to build up to the answer, since these numbers are the start of the sequence.

After reaching a base case, the method can begin returning, computing each new Fibonacci number from the values returned by its recursive calls. We'll return to Fibonacci in the next reading, and get more specific then. The key here is to remember that a recursive method needs at least one base case to make sure the recursion stops at some point, and the methods start returning results.

Using Recursion for Repeated Actions: Nesting Doll Example

Let's use a metaphor to look at the difference between solving a problem iteratively versus recursively. Imagine you have a large nested doll, containing an unknown number of smaller nested dolls within it. Our goal is to determine how many dolls are contained within the largest nested doll and we're going to look at some different ways to determine this.

Figure 2. An animation of nesting dolls being opened and put back together. A large doll is pulled in half. It is revealed to be hollow and contain another doll inside of it. That doll is removed. Once again the top of the doll is removed from the bottom. This is repeated two more times revealing smaller dolls until a tiny doll is revealed that is solid.

Figure 2. Nesting dolls being opened and put back together.

Let's imagine we have a nesting doll class that looks like:

public class Doll {
    // If there is no doll inside of this one, innerDoll will be null.
    private Doll nested;

    // Can be used to create the smallest doll with no doll inside of it.
    public Doll() {
    }

    // Can be used to create a doll with another doll inside of it.
    public Doll(Doll nested) {
        this.nested = nested;
    }

    public boolean doesOpen() {
        return nested != null;
    }

    public Doll getInnerDoll() {
        return nested;
    }
}

Iterative

To open the doll iteratively, we might imagine using a while loop. The code of the method might look something like this:

public Doll findSmallestDollIterative(Doll outerDoll) {
    Doll smallestDoll = outerDoll;
    while (smallestDoll.doesOpen()) {
        smallestDoll = smallestDoll.getInnerDoll();
    }
    return smallestDoll;
}

In this example, our code checks if the current smallestDoll is able to open, looping again each time an openable doll is found. As soon as we find a non-openable doll, the loop ends.

Notice that in this iterative implementation, we employ a loop, but no recursive call, so there will only ever be one stack frame for findSmallestDollIterative on the stack.

Figure 3. The stack and heap for the iterative nesting dolls example. The only call to findSmallestDollIterative is at the bottom of the stack. It starts by initializing the smallestDoll to the outerDoll variable passed to the method. For each execution of the while loop, it checks to see if the doll can open, i.e. that the nested doll is not null, and if it can, it gets the inner doll and reassigns smallestDoll to the inner doll. This repeats until a call to doesOpen returns false, causing the while loop not to execute. At this point the smallestDoll is returned.

Recursive

To open the doll recursively, we will need to think about what our repeated action will be (our recursive case) and what our terminating case will be (our base case).

• Base case: We've found a doll that doesn't open. We've found the smallest doll: return it.
• Recursive case: We've found a doll that does open. Call the method again on the inner doll.

Such a method might look like this:

public Doll findSmallestDollRecursive(Doll doll) {
    if (!doll.doesOpen()) {
        // base case: unopenable doll
        return doll;
    } else {
        // recursive case: call method on doll's inner doll
        return findSmallestDollRecursive(doll.getInnerDoll());
    }
}

In this example, findSmallestDollRecursive first checks to see if we have a doll that doesn't open. This is the base case. If we find such a doll, we've completed the task and can return the current doll.

On the other hand, if the doll does open, we've found a recursive case. Call the method again, passing in the current doll's inner doll.

Each call to findSmallestDollRecursive will create another call to findSmallestDollRecursive, until the base case is encountered. In this case, we will have one findSmallestDollRecursive stack frame for each doll encountered. Each successive stack frame receives a smaller doll as its input parameter, so though there are many stack frames for the same method, each has a different input representing its particular recursive case.

Figure 4. The stack and heap for the recursive nesting dolls example. The first call to findSmallestDollRecursive is at the bottom of the stack. It checks to see if the doll can open, i.e. that the nested doll is not null, and if it can it recursively calls findSmallestDollRecursive passing in the Doll nested within. This repeats until a call to findSmallestDollRecursive is made with a Doll whose nested Doll is null (base case), at which point the methods will begin returning, unwinding the stack.

Notice that if we checked for the base case after handling the recursive case, our function would never end and we would run into a stack overflow or NullPointerException. The base case should be handled before making a recursive call.

Returns in Recursion: Maze Example

Let's look at another example that focuses on the importance of returns in recursion.

Imagine you are trying to find your way through a maze. You begin at the maze entrance and your goal is to find your way out. You make a recursive call each step, evaluating the paths available to you at that step.

With each step, you check all paths. If multiple paths exist, you consider each path available to you, trying recursively to exit the maze through each path.

• (Base case 1) If the current location is an exit, we're done!
• (Base case 2) If the current location is a dead end, we know we need to backtrack.
• (Recursive case) If the current location is neither a dead end nor an exit, we recursively attempt to find an exit down each path in front of us by calling the recursive function once for each path option. When each path returns from its recursive call to exit the maze:
  • If this path eventually led to an exit, we'll receive a path to the exit from the recursive call. Add the current location to the beginning of the path.
  • If all options down this new path are dead ends, we will receive a false from the recursive call. Try the next path option in front of us.
  • If we've exhausted all paths in front of us, return false.

Figure 5. Diagram of the map. There are 4 steps with numbers to represent decision points; in the first step 1 is being explored, 2 is unexplored. In the second step 1 was explored, 2 is unexplored, 3 is being explored, 4 is unexplored. In the third step 1 was explored, 2 is unexplored, 3 is being explored, 4 is unexplored, and 5 is a dead end. In the fourth step 1 was explored, 2 is unexplored, 3 was explored, 4 is the way out, and 5 is a dead end.

The maze example demonstrates a more sophisticated series of actions and choices than the nesting doll example because we might be making two or three recursive calls at each recursive step rather than always one. It also has two base cases (as with Fibonacci) rather than the one base case for the nested dolls.

We want to again emphasize the need to implement base cases to avoid infinite recursion (making nested recursive calls until we get a stack overflow error). In this example, if we didn't return when we found the maze exit, or we didn't return a value indicating that we'd reached a dead end, we'd be stuck in the maze forever!

As demonstrated in the nesting doll example, many problems solvable with recursion could also be solved iteratively (with loops). In the next reading we will dig deeper into why recursion might be a better choice for solving certain problems, and how to decide between the two approaches for problems that you're trying to solve.

Pros and Cons of Recursion

Recursion or iteration? Choosing between the two

As mentioned in the last reading, recursive methods break problems into slightly simpler problems and call themselves recursively until reaching a base case. Iterative methods use loops to perform an operation once per loop until the problem is solved. Often either approach could be used to solve a particular problem, and you'll want to think about which would be more appropriate for a given situation. In this reading we'll look at some code examples and consider when and why you might want to choose to implement recursive methods over iterative ones, and vice versa.

We'll start by looking at the Fibonacci sequence, which we mentioned in the previous reading. First, let's dive deeper into the Fibonacci sequence itself, and then we'll move on to exploring how to compute the sequence recursively.

The Fibonacci sequence is a sequence of numbers in which each number is always the sum of the previous two numbers in the sequence. The most common Fibonacci sequence begins with the numbers 0 and 1. (Note that you need both starting numbers to define a Fibonacci sequence in order to compute the rest; with only one number we can't compute the second one in the sequence!). Traditionally, the "first" element in the sequence is actually called the zeroth element, just like our arrays and Lists are zero-indexed:

Fib sequence number	how we compute it	Sequence so far
0th	0 (given to us!)	[0]
1st	1 (given to us!)	[0, 1]
2nd	0th + 1st = 0 + 1 = 1	[0, 1, 1]
3rd	1st + 2nd = 1 + 1 = 2	[0, 1, 1, 2]
4th	2nd + 3rd = 1 + 2 = 3	[0, 1, 1, 2, 3]
5th	3rd + 4th = 2 + 3 = 5	[0, 1, 1, 2, 3, 5]
6th	4th + 5th = 3 + 5 = 8	[0, 1, 1, 2, 3, 5, 8]
7th	5th + 6th = 5 + 8 = 13	[0, 1, 1, 2, 3, 5, 8, 13]

Figure 1. A diagram of the first few steps in the Fibonacci sequence. The list reads {0, 1, 1, 2, 3, 5, 8, 13...}. The diagram shows that the sum of the first two numbers {0, 1} equals the third number {1} and the sum of the second and third number {1, 1} equals the fourth number {2}.

The Fibonacci sequence lends itself to a recursive interpretation and implementation:

• Its definition is recursive: Each term is defined in terms of prior values of the sequence
• This problem breaks down into a short computational step (add the two previous numbers and insert the result at the end of the sequence)
• Each step performs the exact same operation, on a different pair of numbers
• As we'll see below, the iterative solution requires some careful bookkeeping of the current 'state' of our computation, as we track past/current values in the sequence

Fibonacci sequence: recursive solution

Each time we want to Compute fibonacciRecursive(n) and we are not in a base case of n == 0 or n == 1, we need to perform these three actions:

1. Compute fibonacciRecursive(n-2)
2. Compute fibonacciRecursive(n-1)
3. Return fibonacciRecursive(n-2) + fibonacciRecursive(n-1)

If we look at the 4th fibonacci sequence number in the chart above, n = 4, we need to perform these three actions:

1. Compute fibonacciRecursive(2), because n - 2 = 4 - 2 = 2.
2. Compute fibonacciRecursive(3), because n - 1 = 4 - 1 = 3.
3. Return fibonacciRecursive(2) + fibonacciRecursive(3)

Fib sequence number	how we compute it	Sequence so far
4th	2nd + 3rd = 1 + 2 = 3	[0, 1, 1, 2, 3]

The outline below demonstrates finding the 4th Fibonacci value. We have nested these calls to show the sequence that the computation and method calls would be made in. The first call to fibonacciRecursive(4) requires calls to both fibonacciRecursive(3) and fibonacciRecursive(2), which each require further recursive calls. However, when the calls to fibonacciRecursive(3) and fibonacciRecursive(2) return, we add them and return the result.

Compute fibonacciRecursive(4)
    Compute fibonacciRecursive(3)
        Compute fibonacciRecursive(2)
            Compute fibonacciRecursive(1)
                Return: 1
            Compute fibonacciRecursive(0)
                Return: 0
            Return: fibonacciRecursive(1) + fibonacciRecursive(0) == 1 + 0 == 1
        Compute fibonacciRecursive(1)
            Return: 1
        Return: fibonacciRecursive(2) + fibonacciRecursive(1) == 1 + 1 == 2
    Compute fibonacciRecursive(2)
        Compute fibonacciRecursive(1)
        Compute fibonacciRecursive(0)
        Return: fibonacciRecursive(1) + fibonacciRecursive(0) == 1 + 0 == 1
    Return: fibonacciRecursive(3) + fibonacciRecursive(2) == 2 + 1 == 3

Looking deeper into what is required to compute fibonacciRecursive(3), as an example:

• It requires calling fibonacciRecursive(2) and fibonacciRecursive(1)
• fibonacciRecursive(1) is a base case, returning 1.
• fibonacciRecursive(2) requires calling fibonacciRecursive(1) and fibonacciRecursive(0)
  • These are both base cases, returning 1 and 0, respectively
• fibonacciRecursive(3) can now add the results from fibonacciRecursive(2) and fibonacciRecursive(1) to get 1 + 1 == 2

One detail that you may have noticed: if n is negative, the algorithms above will run forever (or until they run out of memory). If writing very robust code, we can check for this case and throw an exception, rejecting the input to avoid errors. Our code will ignore this case and assume that all parameters are non-negative.

Let's write the Fibonacci number generator. It needs to receive a position in the sequence to compute, and returns the number at that position in the sequence, so the signature might be:

public int fibonacciRecursive(int position) {...}

As discussed above, our two base cases to check for are the 0th and 1st Fibonacci numbers when n is 0 or 1, which will return 0 and 1, respectively. Let's add our base cases:

public int fibonacciRecursive(int n) {
    // base case 1
    if (n == 0) {
        return 0;

    // base case 2
    } else if (n == 1) {
        return 1;
    } ...
}

We can simplify this a bit, taking advantage of the fact that the base cases return the same number as n, the 0th fibonacci number is 0 and the 1st fibonacci number is 1:

public int fibonacciRecursive(int n) {
    // base cases
    if (n == 0 || n == 1) {
        return n;
    }
    ...
}

We've defined our base cases, so our recursion will eventually end. We still need to add our recursive case, calling this method again on a slightly smaller problem.

The following line of code returns the sum of two recursive calls to our method fibonacciRecursive, the first with (n - 2) and the second with (n - 1). This sets up the two paths that the sequence goes down, as shown in the diagram from above.

return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);

Now, let's put that all together and see what it looks like.

public int fibonacciRecursive(int n) {
    if (n == 0 || n == 1) {
        // base cases
        return n;
    }

    return fibonacciRecursive(n – 2) + fibonacciRecursive(n - 1);
}

This code works just like our diagram up above illustrates. If we pass the number, 0, to the function, it will hit our first base case and return 0. If we pass the number, 1, it will hit our second base case and return 1. If we pass in a number greater than 1, the function will use the recursive case to call itself again twice: once for n minus 1, and once for n minus 2. It then adds and returns the sum of these two results.

Can you think of how many times the method is called to compute the value for n = 4? (hint: take a look at the tree diagram above: which elements of the diagram represent method calls?)

Fibonacci sequence: iterative solution

Recursion isn't our only option for solving this problem. We could also write a loop that would find the nth number in the sequence using a loop, instead of a recursive call. Here's what that would look like:

Figure 3. Diagram showing an iterative solution for the Fibonacci sequence when n = 6. Each step adds together two numbers---the first number becomes the second number in the next step, and the sum of the numbers becomes the first number in the next step. The values are: first step, 1 + 0; second step, 1 + 1; third step, 2 + 1; fourth step, 3 + 2; fifth step, 5 + 3, sixth step is n = 6 and our final value is 8.

Our recursive method started with the position we needed to identify and worked down, breaking each case into smaller and smaller pieces until we reached the first two numbers in the sequence before adding the results back up. In contrast, our iterative solution to the Fibonacci sequence begins at the bottom, with the first numbers in the sequence.

In each iteration, our loop needs to keep track of three numbers:

• the previous number
• the previous previous number
• The current number, computed by adding the above two.

In the first instance of the loop our two numbers are 1 and 0, which we add to compute the current number, 1 (in this case, the 2nd number).

Here's where we've got to pay close attention! In the next loop:

• Our previous number value is assigned to our previous previous number variable
• Our current number value is assigned to our previous number variable
• We add these two together to get the next current number

In the first iteration or two, it can be difficult to see the pattern, as many of the numbers are 1s. However, let's look at what happens when the sequence gets a bit longer. On line three (our 3rd fibonacci number) our previous number has been updated to 2, and our previous previous number is 1. We add these together to compute a current number of 3. On line four, previous number's value (2) is assigned to our previous previous number variable, and our current number (3) is assigned to our previous number variable. Our new current number is their sum, 5.

Now let's see the code. The method signature is similar to the recursive method, as we still need to pass in an integer letting the method know which position in the sequence we're looking for.

public int fibonacciIterative(int n) {...}

For our loop to work we'll need to define three variables:

• previous number
• previous previous number
• current number

We'll initialize our variables, pretending that we "computed" the 0th and 1st sequence numbers. We'll decide to compute the current number at the top of our loop accordingly (there are other ways to order the computations and intializations, so this is a little arbitrary)

public int fibonacciIterative(int n) {
    int previousPreviousNumber = 0;
    int previousNumber = 1;
    int currentNumber;
    ...
}

With our variables declared, we can start our loop. We want to loop for as long as i is less than the n value we passed the method when we called it. As we are starting at 1, this loop will work for all cases where n is greater than or equal to 2.

In order to handle the 0th and 1st sequence numbers, let's check for them at the start of our method

public int fibonacciIterative(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }

    int previousPreviousNumber = 0;
    int previousNumber = 1;
    int currentNumber;
    ...
}

Which we can simplify as we did above in the recursive case:

public int fibonacciIterative(int n) {
    if (n == 0 || n == 1) {
        return n;
    }

    int previousPreviousNumber = 0;
    int previousNumber = 1;
    int currentNumber;
    ...
}

We need to iterate through the numbers, from 1 up to n, and for each of them:

1. Add the previous-previous number to the previous number to compute the current Fibonacci number: currentNumber = previousPreviousNumber + previousNumber;
2. Update previousPreviousNumber to the value of the old previousNumber: previousPreviousNumber = previousNumber;
3. Finally, update previousNumber to the value of the current Fibonacci number we just computed: previousNumber = currentNumber;

Putting it all together:

public int fibonacciIterative(int n) {
    if (n == 0 || n == 1) {
        return n;
    }

    int previousPreviousNumber = 0;
    int previousNumber = 1;
    int currentNumber;

    for (int i = 1; i < n; i++) {
        currentNumber = previousPreviousNumber + previousNumber;
        previousPreviousNumber = previousNumber;
        previousNumber = currentNumber;
    }

    return currentNumber;
}

In this example, once our method takes in our input for n it loops through the for loop, adding up the members from the start of the sequence, instead of subtracting down from the end of the sequence through the indices as the recursive method did. We continue adding then updating our previous previous and previous numbers until we have run the loop for the requested number of positions in the sequence.

Pros and cons of recursion

Now that we've seen an example of some problems solved both recursively and iteratively, let's consider why you might select one or the other in your code.

Readability

When deciding between recursion and iteration, one thing you want to weigh is readability. Recursive functions for appropriate problems can sometimes be shorter and may be easier for people to read. The Fibonacci methods demonstrated here aren't that different, though the recursive one requires fewer state variables to keep track of and is arguably easier to read (do you think so?). Method complexity will vary depending on what you are trying to implement. Recursive functions often define their base cases up front, so they may be easier for other developers to follow the logic.

But if you look at finding the smallest nesting doll from the previous reading, you could argue that the iterative solution is easier to read.

Memory

While readability may make it easier for other users to read and understand how your methods are working, there is a possible drawback to using recursion that is important to keep in mind. A recursive function keeps all its cases open on the stack while it is recursing toward a base case. Recursive methods thus often consume substantially more stack memory than iterative solutions. One danger is creating a stack overflow error, as the stack continues to collect all of our recursive cases and the variables stored in each frame until we encounter a base case. Even if you don't create a stack overflow, you can still consume a lot of memory, slowing your application down.

In our Fibonacci example, the iterative version of the method only stores three variables ever: previousPreviousNumber, previousNumber, and currentNumber. The recursive function, on the other hand, creates an entire stack frame for each time the method is called. If we run it against fairly small numbers, the difference between in memory usage between the two approaches will be minimal. However, if we use the recursive method to find a large Fibonacci value, the recursive version will quickly consume a lot of memory, and eventually run into memory issues/stack overflow (and in both approaches, we might need something bigger than an int to store the resulting values!).

Backtracking

Let's think back to our maze example from the previous reading. If we are searching recursively for the exit to the maze, we are keeping track of every potential way we could go as we move through the maze. This is important for understanding how recursion uses the JVM's stack: we are holding all our recursive cases in our memory as we continue to search for our base case. Here it arguably helps simplify the solution, as the potential moves we haven't yet considered are "saved" on the stack if we need them, rather than in some complicated data structure that we keep up to date in each iteration of a loop.

This is a common pattern called "backtracking." Backtracking solves problems by exploring all potential solutions until we find out that a potential solution doesn't work. It then goes to where we could have made a different decision and explores that subset of potential solutions. We often use recursion to solve backtracking problems.

This is an example of a tradeoff between code simplicity/readability and memory consumption. It'll depend on the problem you're solving which solution will be easier to read, and if the recursive solution seems simpler, whether it's worth the extra memory consumption.

For these reasons, sometimes it's best to implement something iteratively instead of recursively if the memory consumption will grow out of control in the recursive case. For example, we generally look through a List using an iterative method -- we construct a 'for' loop that iterates through the List until we find the number we're looking for or get to the end of the List. We could do this recursively (check if the current value is the value of interest, and if not, recursively search the "rest of the list"), but for this application it's probably best to stick with iteration for the reasons mentioned above. An unexpectedly large list could lead to stack overflow errors.

Simplifying Problems

Recursion tends to work best when it can break down a large problem into multiple cases of smaller versions of the original problem (while not running out of memory). The Fibonacci example is one to keep in mind, as it models breaking a problem down into simple repeated steps that directly use the results of those steps. Since searching a List doesn't need to be broken down into smaller parts, there's no real benefit of using recursion. It is likely that a recursive method in this case would be confusing and use more memory than an iterative function.

Ultimately, it's important to remember that not everything needs to be done recursively -- it should be a conscious decision to use recursion, and sometimes iteration is better. Hint: you'll usually want to consider the iterative case first, and if it seems too messy, take a look at the recursive approach you might implement. You'll probably most often use iteration, but it's important to have recursion in your toolbox for when it really fits.

Developing a Recursive Algorithm

Designing a Recursive Algorithm

In this section we will use something called binary search to further explore recursion. After describing the binary search algorithm, we will implement binary search with a recursive method.

Binary search

A binary search algorithm is a way to find a value (or whether that value is absent) in a sorted array or list. A binary search first finds the value at the middle index in the sorted array. If the value you're looking for is the value at that index, then you're done, return the index! If the number you're looking for is lower than that middle value, the search is repeated on just the sub-array before the middle index. If the number you are looking for is higher than the middle value, the search is repeated on the sub-array after the middle index. A binary search algorithm repeats this process, looking at the middle value of smaller and smaller pieces of the array until it finds the value you're looking for or runs out of middle values to check (in which case the value of interest is not in the array).

The advantage of searching an array this way is speed: each time the search algorithm splits the array in half, it discards half of what is left, moving closer and closer until it finds the value you are looking for or determines that the value you're looking for doesn't exist. This means the search can be completed in logarithmic O(log n) time, which is better than the linear O(n) time if we linearly searched the array from beginning to end. (This all of course depends on the requirement that the array is sorted to begin with!)

Figure 1 demonstrates how binary search works. In this example, we are looking for number 23, which happens to be at index 5 in the array. Binary search keeps track of three values---the lower bound, the upper bound, and the middle value. When the search algorithm splits the array in half, it determines which half of the array to discard based on whether the middle value is higher or lower than the value it's looking for:

If the middle value is higher than the search value:

• We ignore the upper half of the array
• The lower bound remains the same
• The upper bound becomes the middle value
• Recursively binary search the smaller array

If the middle value is lower than the search value:

• We ignore the lower half of the array
• The lower bound becomes the middle value
• The upper bound remains the same
• Recursively binary search the smaller array

The middle value is then updated to the value in the middle of the new (smaller) array. The process continues until the correct value is found (or the array size reduces to 1).

If we compared each number in the array in sequence beginning with the zeroth index, we would find 23 on our sixth comparison. However, using the binary search method, we are able to find 23 after only three comparisons. The difference is magnified with much larger arrays, as linear search runs in linear O(n) time, and binary search runs in logarithmic O(log n) time.

Figure 1. Diagram of Binary Search when searching for the value 23 in index 5. There are 4 steps; the first step sets up the array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. In the second step the index of the lower bound is L = 0, the index of the middle value is M = 4, and the index of the upper bound is H = 0. In the third step we're only looking at the upper half of the array, L = 5, M = 7, and H = 9. In the fourth step we're only looking at the lower half of the previous array, L = 5, M = 5, and H= 6. The value 23 is in index 5, so we have found the value we're looking for.

Writing a recursive binary search method

Reminder: this will only work if the array is sorted. The method we're writing will not verify this, so it's the responsibility of the calling code to ensure that it's sorted. If not, the results are unpredictable and it's the calling code's fault!

When writing a recursive algorithm, we always want to start with identifying our base cases. The target value that we're searching for is the primary base case. Once we find our target value, we're done searching and don' need to call the method again.

A secondary base case is needed as well to account for the case when our recursive function runs out of array indexes to check and still has not found the value we're looking for. This occurs when the higher bound and lower bound have crossed each other, e.g our higher bound is 4 and our lower bound is 5. If we had been looking for the number 20 in figure 1 above, the number we were looking for, 20, would have been less than the middle number, 23. The next run of the algorithm would have left the lower bound where, L = 5 and moved the higher bound to be directly on the left side of the middle index we just checked. That means our next higher bound would have been H = 4. If the target value isn't found in the array, we will return -1 to indicate value not found.

However, if we find a number that's not our target value, we have a recursive case. In this instance we will want to call our method again, searching a subset of the larger array until we find our target value. The repeated action we want to perform is a comparison, checking our target value against the number in the middle position of our ever-shrinking observed section array determining if it is equal, larger, or smaller.

Our search method will need a few things:

• Array to search
• Value to search for, which we'll call targetValue
• Variables to keep track of the current search array's lower and upper bounds.

At the end of our method we will have a return of -1 to let us know that the array does not contain the value we are searching for.

/**
 * Uses binary search to find the index of the targetValue in
 * the sorted array, arr.
 */
int binarySearch(int arr[], int start, int end, int targetValue) {
    if (start <= end) {
        int middle = start + (end - start)/2;

        if (arr[middle] == targetValue) {
            return middle;
        }
        if (arr[middle] > targetValue) {
            // we know it's not at middle, so end can be one lower
            return binarySearch(arr, start, middle - 1, targetValue);
        }
        // we know it's not at middle, so start can be one higher
        return binarySearch(arr, middle + 1, end, targetValue);
    }
    return -1;
}

Let's break down this method. In the first if statement we check to see if there are still values in the array. If so, we find the middle of the array and save that to the variable middle.

When finding the middle position of the array, if the array has an odd number of indices, then the following line will perform integer division and drop the 0.5 value and return the smaller number.

int middle = start + (end – start) / 2;

In the case of binary search, this works in our advantage!

Now we find the middle position of our array and compare that number to the number in our targetValue. If they are equal, we have found our base case! We simply return that position and exit the method.

If they are not equal, we check to see if our key is bigger or smaller than our middle value. If our key is smaller, it must be in the subarray with values below our middle point. If it is larger, it must be in the subarray with values larger than our middle point. We call the binarySearch method again, searching only half the values we previously searched and ignoring the rest.

Check out the code and see if it works in all cases you can think of. Using the debugger may help you see the algorithm in action.

We can use binary search for more than integer arrays

Our example was searching for integers in an array. But the algorithm can certainly be extended to Lists, and it can be used to search for any arbitrary value or object, not just ints. We could, for example, be searching a List<Person> to find a Person object whose name matched "Felicia". If the List is already sorted, we can perform a binary search, comparing the name of each Person with "Felicia", and following the algorithm in the same manner as above.

Fibonacci Sequence Example

The Fibonacci sequence is a classic example for demonstrating recursion. Each number in the sequence is the sum of the two preceding ones, typically starting with 0 and 1.

The sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Recursive Implementation

public int fibonacciRecursive(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return n;
    }
    
    // Recursive case
    return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
}

Iterative Implementation

public int fibonacciIterative(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    int prev = 0;
    int current = 1;
    int result = 0;
    
    for (int i = 2; i <= n; i++) {
        result = prev + current;
        prev = current;
        current = result;
    }
    
    return result;
}

Comparison

While the recursive implementation is more elegant and closely mirrors the mathematical definition, it has exponential time complexity O(2^n) due to repeated calculations of the same values. The iterative version has linear time complexity O(n) and is more efficient, especially for larger values of n.

Factorial Example

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It's often denoted as n!.

For example, 5! = 5 × 4 × 3 × 2 × 1 = 120

Recursive Implementation

public int factorialRecursive(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // Recursive case
    return n * factorialRecursive(n - 1);
}

Iterative Implementation

public int factorialIterative(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    
    return result;
}

In this case, both implementations have linear time complexity O(n), but the recursive version has additional overhead due to function calls and stack frame management, making the iterative version generally more efficient.

When to Use Recursion

Consider using recursion when:

• The problem can be naturally divided into similar subproblems
• The solution is easier to express recursively (like with tree traversals)
• Time and space complexity aren't critical constraints
• The recursion depth is limited and won't cause stack overflow

Avoid recursion when:

• The recursion depth could be very large (potentially causing stack overflow)
• Performance is a critical concern and a more efficient iterative solution exists
• The problem doesn't naturally break down into similar subproblems

Practice

Guided Project