Recursion sample problem

The second midquarter assessment task will be recursive problem-solving. The problem statement will follow the structure of the many recursive examples we have seen in lecture, section and assignments. You are given a problem description and function prototype and are asked to design and implement a solution. Your answer is to be presented in C++ code. We will not be especially picky about details of C++ syntax, but answer should be much closer to valid code than, say, pseudocode. It is totally okay to not get to the point that you have a complete solution by the time that you start the discussion period with your section leader – part of your time during the discussion period can be spent fleshing out the final details of the complete solution alongside your section leader.

In the discussion portion of the assessment, you will present your solution. You should be prepared to describe your recursive strategy for solving the problem. You may do this by sketching a decision tree, comparing your approach to that taken by a similar problem, and/or tracing through the operation on a simple example.

You should also be be prepared to analyze your code and explain such things as the mechanics of how your code operates, how state is maintained through the recursive calls, how different choices are explored, how base cases are structured, what test cases would be useful to confirm the correctness of your code, and so on.

You may be also asked to discuss the effect of certain changes to the code (what happens if move this base case ahead of that one?) or to propose changes that would be necessary to achieve a certain effect (how could you change the function to count all solutions instead stop at first?)

The primary skills being assessed for this task is your facility with recursive problem-solving and understanding of the mechanics of recursion and backtracking.

Sample problem statement

Write a recursive function divide that uses backtracking to divide the letters from word w into two words s1 and s2. Each letter from w must be used exactly once either in s1 or s2, and the relative order of the letters must be preserved, meaning that s1 and s2 must both be subsequences of w.

For example, the word "friendly" can be divided into "find" + "rely". This solution is valid because s1 and s2 together contain all of the letters from w, the letters in s1 and s2 appear in the same relative order as they did in w, and both s1 and s2 are valid words.

For some words, no valid division is possible. For example, consider dividing the word "stream". It would not be valid to divide into "star" + "me" (order of letters not preserved), nor "stem" + "ram" (reuses 'm'), nor "stem" + "a" ('r' not used), nor "seam" + "tr" (not in dictionary).

You will be passed two parameters: a string w to divide, and a reference to a Lexicon of dictionary words. If the function finds a valid division, it prints the two words and searches no further. If no valid division is found, the function prints nothing. The function should also return a bool value of true if a division was found and printed, or false if not.

Use the Lexicon passed to ensure that the divided words are both found in the dictionary. You must also use it to optimize your exploration by avoiding paths that cannot possibly lead to a valid solution.

The following table lists some example calls to your function, the expected return values, and possible output to appear on the console, given a Lexicon called lex:

Call Returns Possible output
divide(lex, "friendly") true find + rely
divide(lex, "standing") true sting + and
divide(lex, "midterm") true mid + term
divide(lex, "recuperate") true cure + repeat
divide(lex, "stream") false  

If there are multiple valid divisions for word w, you may print any of them. Regardless of which division you print, your code must stop after finding a single solution; do not find/print all possible solutions.

You will need to write a helper function.

For full credit, your solution must obey the following restrictions.

Solution 
void divide(Lexicon& lex, string input) { 
    divideHelper(lex, input, "", "");
}

bool divideHelper(Lexicon& lex, string input, string left, string right) { 
    if (input.empty()) {
        if (lex.contains(left) && lex.contains(right)) { 
            cout << left << " + " << right << endl; 
            return true;
        } else {
            return false;
        }
    } else if (!lex.containsPrefix(left) || !lex.containsPrefix(right)) {
        return false;
    } else {
        char ch = input[0];
        string rest = input.substr(1);
        return (divideHelper(lex, rest, left + ch, right)
                 || divideHelper(lex, rest, left, right + ch));
    }

Additional practice

Other selected recursive problems for review/practice.

General advice

Here is some on recursive problem solving in the context of exams/assessments: