University of Toronto
CSC148--Introduction to Computer Science, Fall 1997
Assignment 3: Recursion

Due:  Thursday 20 November, 6:00 pm
This assignment is worth 10 marks towards your grade in this course.

This assignment consists of several separate questions, all involving recursion. The questions start out very easy and get harder.  

Question 1

Below is a recursive method that prints out all possible strings of a given length containing only letters from a given set (represented by a string of distinct characters).

    // "sofar" keeps track of the front of the string that we've generated so far.
    public static void recPrintCombos (String charSet, int n, String sofar) {
       if (n == 0)
            System.out.println(sofar);
       else
            for (int i=0; i<charSet.length(); i++)
                recPrintCombos (charSet, n-1, sofar+charSet.charAt(i));
    }

Note that the same letter may be chosen out of the set more than once for use within a single output string. For example, if the set of letters were represented by string ``abcde", then the possible strings of size 3 that can be made up of letters from this set include: ``aaa", ``abc", ``acd", ``ebc", and ``eeb".  

The method requires an extra parameter called sofar to help keep track of what's going on during the recursion. However, the caller of the method shouldn't have to be aware of this extra parameter. To make a nicer interface for the caller, we can provide a second method that merely sets things up and calls the recursive one.

     public static void printCombos (String charSet, int n) {
         if (n > 0)
              recPrintCombos (charSet, n, "");
         else
              System.out.println("There are no strings of that length");
     }

Your task is to trace in careful detail the following method call:

     recPrintCombos ("123", 2, "");

What to hand in: Just your trace.  

Question 2

Part (a): Write a recursive method that returns the sum of all the elements in a given array of ints, between positions ``start'' and ``finish'' inclusive. Use the following signature:

     public static int total1 (int[] A, int start, int finish)

Your method must reduce the size of the problem by one element each time it recurses.  

Part (b): Write a second version of this method, called total2, but this time write it so that it reduces the problem size by roughly half each time it recurses. Use the same parameter list as for method total1.  

Part (c): Compare the efficiency of the two functions total1 and total2, in terms of the number of array accesses required. You can answer this question informally, without using recurrence relations.  

What to hand in: Hand in just the two functions and your written or typed answer to part (c). Don't hand in test runs, although, of course, you should still test your methods thoroughly for yourself to make sure that they work.  

Question 3

Below is a method that checks to see whether or not a string is a ``palindrome'' -- a string that reads the same backward or forward.

        public static boolean isaPalindrome (String s) {
            if (s.length() <= 1)
                return true;
            else if (s.charAt(0) == s.charAt(s.length()-1)) 
                return isaPalindrome (s.substring(1, s.length()-1));
            else
                return false;
        }

Note that the Java String method substring(int offset, int endIndex) returns the substring between positions offset and endIndex-1 inclusive.  

Let S(n) represent the following statement: ``if isaPalindrom is called with a string of length n, the method returns true if the string is a palindrome and false otherwise.'' Prove that S(n) is true for all n >= 0.  

What to hand in: Your proof.  

Question 4

A trie is a data structure that stores strings in a way that makes searching efficient. (The word ``trie'' comes from the middle of the word ``retrieval''; it is pronounced ``try'' in order to distinguish it from the word ``tree''.) Perhaps the most common use of a trie is for storing a spelling dictionary. When used this way, each node in a trie stores a single letter, plus one reference for each letter in the alphabet. If you follow any path in the trie starting from the top or ``root'' node, the sequence of letters encountered defines a string; each node in the trie also stores a boolean to indicate whether or not the string from the root to that node is a complete word.  

The following Java class defines a trie node, out of which tries can be built:

     class TrieNode {
        public static final int ALPHABET_SIZE = 26;

        public char letter;
        public boolean isWord;
        public TrieNode [] children;

        // Constructor.  Makes an trieNode with the given character `c'
        // in it, with isWord set to the value `b', and with null children.
        public TrieNode (char c, boolean b) {
            letter = c;
            isWord = b;
            children = new TrieNode[ALPHABET_SIZE];
        }
     }

Figure 1 contains a small example of a trie; one into which the words ``arm'', ``army'', ``art'', and ``top'' have been inserted. The trie indicates that ``ar'' and ``a'' are just prefixes of some other words that have been inserted into the trie, not words themselves, by storing false at that ``a'' and ``r'' nodes. Although ``to'' is in fact a word and nodes for the letters ``t'' and ``o'' already exist in the trie in the right places to represent ``to'', that ``o'' node does not have a true as it would if ``to'' had been inserted into the trie. Note that the root node of the trie is special; it contains a blank. Think about why we need this special node to get things started.  

The letter stored in each node is in fact redundant; the array position (in the parent node) of the pointer to a node can be used to determine which letter the node represents. For instance, the ``o'' node in figure 1 is pointed to by the 14th pointer in its parent node because ``o'' is the 14th letter of the alphabet, counting from zero.  

  
Figure 1: A trie into which the words ``arm'', ``army'', ``art'', and ``top'' have been inserted.

For this part of the assignment, you are to write a Java class called Lexicon, that stores a set of strings using a trie. Your class must have a method to perform each of the following operations:

• Insert a given string into the lexicon.
• Build a whole lexicon by repeated insertions of strings from a given file. We will provide you, on the web, with information about how to read from an input file.
• Check if a given string is in the lexicon.
• Print all strings in the lexicon.
  Hint: When recursing through the trie, use a string parameter to keep track of the string from the root to the current node.
• Print all strings in the lexicon that share a given prefix.
  (The fact that this operation is quite simple to implement is one of the nice things about a trie.)

Some of these methods can be done elegantly without recursion; others cannot. It will be up to you to decide whether to use recursion, and to design the exact method signatures for these operations. Remember that each recursive method should receive through parameters all information it needs to do the job; it should not access instance variables.  

You are not required to write a complete spelling checker program for this assignment, Just write a test driver.  

What to hand in:

• A printout of your Lexicon class.
• A printout of your test driver and the annotated input and output for your test runs.
• A written report on your testing strategy.
• A written description of any remaining bugs or missing features in your program. Label it ``Bugs and Missing Features''. If you are convinced that there are no bugs or missing features, say so.