S-111
  • Home
  • Lectures
  • Problem Sets
  • Sections
  • Syllabus
  • Schedule
  • Staff
  • Resources
  • Canvas
  • Ed Discussion
  • Gradescope

Section 10

  • Reminder about unit 3 practice test
  • Recursion
  • Exercises

Recursion

Recursion (rĭ-kûr’-zhən) noun. If you still don’t get it, see recursion.
— Michael C. Corballis, The Recursive Mind: The Origins of Human Language, Thought, and Civilization

Recursion is a powerful concept in computer science, and although we will return to it in greater detail, I will present recursion now by contrasting it to iteration. We will explore the iterative and recursive way to solve a problem that requires repetition: writing a method that prints a range of ascending squares.

Here’s the precise method specification:

Given two integers x and y, the method should print the squares of all integers between x and y (including x-squared and y-squared), each on its own line.

The following Java method solves this problem by using a for loop:

public static void printSquaresIterative(int low, int high) {
    for (int i = low; i <= high; i++) {
        System.out.println(i * i);
    }
}

This approach is known as an iterative approach, since the body of the for loop completes one full step of the solution at a time, and there are no method calls to itself. In fact, since there are no method calls whatsoever, this entire problem is solved inside the stack frame for the printSquaresIterative() method.

Here’s a recursive version that will produce the same output:

public static void printSquaresRecursive(int low, int high) {
    if (low == high) {
        System.out.println(low * low);
        // then don't make a recursive call
    } else {
        System.out.println(low * low);
        printSquaresRecursive(low + 1, high);
    }
}

Both approaches run quickly, produce the same output, and take up about same number of lines of source code. However, recall that the recursive method uses the call stack to its advantage.

  1. As we did in lecture, trace the recursive execution of printSquaresRecursive(1, 5). Be sure to keep track of the value of the local variables for each instance of the method, from the initial values, to the base case, and back to the main() method. 1

The real flexibility of recursion as an approach to solving problems comes from the ability to describe the solution in terms of itself.

First, observe that the task of printing the squares of numbers in a range can be solved as long as we know how to square any number. We know we can do this by taking the number and multiplying it by itself. Now we can easily apply the recursive reasoning to the entire range:

Printing the squares of 1 through 5 can be done by printing 1, then printing the squares of 2 through 5.
Printing the squares of 2 through 5 can be done by printing 4, then printing the squares of 3 through 5.
Printing the squares of 3 through 5 can be done by printing 9, then printing the squares of 4 through 5.
Printing the squares of 4 through 5 can be done by printing 16, then printing the squares of 5 through 5.
Printing the squares of 5 through 5 can be done by simply printing 25.

There are two implications of what we just showed. The first implication is that we can collapse this repetitive sequence of operations by turning it into a formula:

Printing the squares of x through y can be done by printing x times x, then printing the squares of (x + 1) through y.

Above, the text “printing x times x” is the part of the problem we can solve directly. The text “printing the squares of (x + 1) through y” is the recursive call, wherein we break our problem into a smaller (or simpler) version and use recursion to solve it.

However, this formula does not include the special case when x equals y. Therefore, we need a base case:

Printing the squares of x through y can be done by printing x times x, then printing the squares of (x + 1) through y. However, if x is equal to y, print x times x and stop.

If you check our definition of printSquaresRecursive() above, you’ll find that the recursive code itself describes the solution to our problem, much more elegantly than the for loop. The only difference is that we check for the base case first.

As we will see in the coming weeks, it seems more natural for some methods to be written recursively, since many problems can be solved by reducing the problem to an atomic sub-problem that is repeated over some input data.

Exercises

  1. Consider the following recursive method:

    public static int mystery(int a, int b) {
    if (a >= b) {
        return b;
    } else {
        return a + mystery(a * 2, b / 2);
    }
}

    Trace the execution of mystery(1, 32) and determine what it will return. In your answer, include the number of frames on the stack when the base case is reached. 2

  2. Write a recursive, static method length that accepts a String parameter and returns the length of the string as an integer. For example, length("Hello") should return 5. In addition, length("") and length(null) should both return 0. 3

  3. Write a recursive, static method repeat that accepts a string str and an integer numCopies and prints the string numCopies times, all on one line. Print a single space between copies of the string. 4

    Make sure that a newline is printed at the very end of the output. For example, repeat("geronimo!", 4) should output the following:

    geronimo! geronimo! geronimo! geronimo!

  4. Write a recursive, static method printTriangular that accepts a string str and an integer height that prints height lines, with height copies of the string on each line. For example, printTriangular("EXTERMINATE", 5) should output the following: 5

    EXTERMINATE EXTERMINATE EXTERMINATE EXTERMINATE EXTERMINATE 
EXTERMINATE EXTERMINATE EXTERMINATE EXTERMINATE 
EXTERMINATE EXTERMINATE EXTERMINATE 
EXTERMINATE EXTERMINATE 
EXTERMINATE

    Hint: make use of your solution to repeat() from the previous question.

  5. Write a recursive, static method numUpperCase that accepts a string str and returns the number of upper case characters in the string. For example, numUppercase("NoNoNo!") should return 3. 6

  6. Write a recursive, static method anyA that accepts a String parameter str and returns true if str has the character a anywhere in str, and false otherwise. If str is null, this method should return false. 7

  1. Here’s the trace, using the indentation style:

    printSquaresRecursive(1, 5) [prints 1]
    printSquaresRecursive(2, 5) [prints 4]
        printSquaresRecursive(3, 5) [prints 9]
            printSquaresRecursive(4, 5) [prints 16]
                printSquaresRecursive(5, 5) [prints 25]
                returns
            returns
        returns
    returns
returns

    At the base case, there are five frames for printSquaresRecursive() and one frame for main(), so six total. ↩

  2. Here’s the trace, using the indentation style:

    mystery(1, 32)
    mystery(2, 16)
        mystery(4, 8)
            mystery(8, 4) returns 4
        returns 4 (value of local a) + 4 (return value from mystery(8, 4))
    returns 2 (value of local a) + 8 (return value from mystery(4, 8))
returns 1 (value of local a) + 10 (return value from mystery(2, 16))

    At the base case, there are four frames for mystery() and one frame for main(), so five total. ↩

  3. Here’s the method:

    public static int length(String str) {
    if (str == null || str.equals("")) {
        return 0;
    }

    return 1 + length(str.substring(1));
}

    ↩

  4. Here’s one solution:

    public static void repeat(String str, int numCopies) {
    if (numCopies <= 0) {
        System.out.println();
        return;
    } else {
        System.out.print(str + " ");
        repeat(str, numCopies - 1);
    }
}

    You could also add another base case to ensure that the last string printed does not have an extra space after it:

    public static void repeat(String str, int numCopies) {
    if (numCopies <= 0) {
        System.out.println();
        return;
    } else if (numCopies == 1) {
        System.out.println(str);
        return;
    } else {
        System.out.print(str + " ");
        repeat(str, numCopies - 1);
    }
}

    ↩

  5. Here’s one solution:

    public static void printTriangular(String str, int height) {
    if (height <= 0) {
        return;
    } else {
        repeat(str, height);
        printTriangular(str, height - 1);
    }
}

    ↩

  6. Here’s one solution:

    public static int numUpperCase(String str) {
    if (str == null || str.equals("")) {
        return 0;
    } else {
        char first = str.charAt(0);

        if (first >= 'A' && first <= 'Z') {
            return 1 + numUpperCase(str.substring(1));
        } else {
            return 0 + numUpperCase(str.substring(1));
        }
    }
}

    You could also use the Character.isUpperCase() method to determine whether the first character is upper case. ↩

  7. Here’s one solution:

    public static boolean anyA(String str) {
    if (str == null ||  str.equals("")) {
        return false;
    }

    else if (str.charAt(0) == 'a'){
        return true;
    }

    else {
        boolean inRest = anyA(str.substring(1));

        if(inRest){
            return true;
        } else{
            return false
        }
    }
}

    ↩

Last updated on July 9, 2025.