Section 15

Advanced string recursion
Recursive backtracking

Advanced string recursion

For the following problems, write a static, recursive Java method as your solution. Your solutions should adhere to the following requirements:

You may not use loops.
You may not use any Java API methods (note: this includes any methods in the String class, like substring or charAt).
However, you may use equals.
You should use the methods head and tail included below.
You can (and should) use any methods developed in earlier problems in your solutions to later problems.

See the below defined head and tail methods:

/*
 * Returns the string containing only the first character of the
 * specified string.
 */
public static String head(String s) {
    return s.substring(0, 1);
}

/*
 * Returns the string containing the all the characters but the first
 * character in the specified string.
 */
public static String tail(String s) {
    return s.substring(1);
}

Write a recursive method spaced that takes a string and returns a new string containing all the characters of the original string, with spaces between each character. ¹
Write a recursive method weave that takes two strings s1 and s2 and returns a new string containing characters of both strings, “weaved” together, starting with s1. For example, weave("abc", "xyz") should return the string "axbycz". If one string is longer than the other, the characters of the longer string should appear after the last character of the shorter string. ²
Write a recursive method startsWith that takes two strings a and b and returns true if a starts with b, or false otherwise. ³
Write a recursive method isSubstring that takes two strings a and b and returns true if a is a substring of b. In other words, the method should return true if b contains zero or more characters, then all the characters of a, then zero or more characters. The method should return false if a does not appear anywhere in b.
Hint: use your startsWith method from the previous task to make this method easier! ⁴
Write a recursive method insertInto that takes a character ch, an integer i, and a string str and returns a new string containing the characters of str, except with ch at position i in the string. The original characters in str from position i to the end should come after ch. For example, insertInto('z', 2, "aaaa") should return a new string "aazaa".
Hint: in the recursive case, you will need to make changes to two parameters being sent to the next call. Which parameters will these be? ⁵

Recursive backtracking

Given a list of words that are to be filled into a crossword puzzle, how can we find a solution to the puzzle that satisfies the following conventional rules of a crossword?

No letter can be inserted into a filled blank.
In a blank where two words intersect, they must share the same letter in that blank.
Words must begin with a numbered blank.
No word can go over the edge of the grid.

We will use the following crossword puzzle as an example:

Use the following possible words: aft, laser, ale, lee, eel, line, heel, sails, hike, sheet, hoses, steer, keel, tie, knot.

Using the recursive backtracking template you saw in lecture, and in your own words, describe what each of the parts of the findSolutions method should do when solving this crossword puzzle example, including:
- what parameters should be passed to a given call of findSolutions() and how to craft the recursive call
- how to know when we’ve found a solution to the crossword
- how to know when a particular possible “step” of the loop is a valid (i.e., how isValid should work)
- how to apply a possible “step” inside the loop (i.e., how applyValue should work)
- how to remove a possible “step” inside the loop (i.e., how removeValue should work)

We will step through the implementation that can be found in Crossword.java. Download the Crossword class and open it in VSCode. You do not need to understand the details of this class — we will just see how findSolutions and isValid work. applyValue and removeValue are somewhat complicated, but their comments are informative.

If you have time, try adding a word to the words array in the main method that would add a possible solution and run the program again. ⁶

Here’s one solution:

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

    return head(str) + " " + spaced(tail(str));
}

↩

Here’s one solution:

public static String weave(String s1, String s2) {
    if (s1 == null || s1.equals("")) {
        return s2;
    } else if (s2 == null || s2.equals("")) {
        return s1;
    } else {
        return head(s1) + head(s2) + weave(tail(s1), tail(s2));
    }
}

↩

Here’s one solution:

public static boolean startsWith(String a, String b) {
    if (b.equals(""))
        return true;

    if (a.equals(""))       // if a is empty and b is not empty,
        return false;       // a *does not* start with b!

    if (head(a).equals(head(b)))
        return startsWith(tail(a), tail(b));
    else
        return false;
}

↩

Here’s one solution:

public static boolean isSubstring(String a, String b) {
    if (a.equals(""))      // "" is substring of any string
        return true;

    if (b.equals(""))      // s1 cannot be a substring of ""
        return false;

    if (startsWith(b, a))
        return true;
    else
        return isSubstring(a, tail(b));
}

↩

Here’s one solution:

public static String insertInto(char c, int i, String s) {
    if (s == null || s.equals(""))
        return "";

    if (i == 0)
        return c + s;       // recursing again is OK, but not needed

    return head(s) + insertInto(c, i - 1, tail(s));
}

↩

See Crossword.java. ↩

Last updated on July 18, 2025.