CS 271 - Data Structures

Optional Recursion Problems

You are NOT responsible for problems like the following ones in CS 271, but they are the next step for those of you who want to take recursion further.  The idea of recursive methods also ties in with the idea of mathematical recursion in CS 211 (Discrete Structures).  More experience with the logic of mathematical recursion helps when you design and use recursive steps in programs.

These problems address the last general situation where recursion is commonly useful (which did not make it into the regular part of the course):  Problems where you recursively find ALL possible solutions, not just one.  This pattern may be easier to figure out if you look at one or two full solutions, and then try to write the rest.

If you do the whole problems here, they are harder than in your assignments and exams, because I do not start off giving you the recursive helping method documentation that sets things up.  (In exams I will use tree situations or other places with recursive definitions, so the recursive pattern should be fairly clear.)

These problems become a lot easier if you read part way into my solution.  There is a fuller explanation under How to reduce the problems to simpler ones.

Parts of this document:

Class skeleton, with method heading, documentation, and full main program

public class ListRecursion {  // skeleton

  // Print all subsets of e, one per line,
  //    assuming all elements of e are distinct.
  public static void subsets(char[] e) {

  // Print all subsets of e with n elements, one subset per line,
  //    assuming all elements of e are distinct, and 0 <= n <= e.length.
  // (This can be derived from previous code, assembling all subsets,
  //   but try to do it more directly.)
  public static void subsetsN(char[] e, int n) {

  // Print out the elements of e in all possible orders,
  //    assuming all elements of e are distinct.
  public static void permute(char[] e) {

  // Return a count of all the sums of subsets of one or more elements from x
  //   that add to sum.  Order does not matter.
  // For simplicity you may assume that all the elements of x are distinct.
  // Again this could be done by finding all subsets, but do it more directly.
  public static int countSums(int[] x, int sum) {
    // code
  }

// complete main program
  public static void main(String[] args) {  // illustration of methods above.
    char[] c3 = {'a', 'b', 'c'};
    char[] c4 = {'a', 'b', 'c', 'd'};
    int[] i3 = {2, 3, 5};
    int[] i6 = {1, 2, 3, 4, 5, 6};
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c3);
    System.out.println("All subsets: ");
    subsets(c3);
    System.out.println("All subsets with 2 elements: ");
    subsetsN(c3, 2);
    System.out.println("All permutatons: ");
    permute(c3);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c4);
    System.out.println("All subsets: ");
    subsets(c4);
    System.out.println("All subsets with 1 element: ");
    subsetsN(c4, 1);
    System.out.println("All subsets with 2 element: ");
    subsetsN(c4, 2);
    System.out.println("All permutations: ");
    permute(c4);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i3.length; j++)
      System.out.print(" " + i3[j]);
    System.out.println();
    System.out.println(countSums(i3, 5)  + " sums adding to 5");
    System.out.println(countSums(i3, 4)  + " sums adding to 4");
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i6.length; j++)
      System.out.print(" " + i6[j]);
    System.out.println();
    System.out.println(countSums(i6, 6)  + " sums adding to 6");
  } // end of main
} // end of ListRecursion

Possible output

The order of your lines could be different.  I added comments on the output in some places after a //.

- - - - - - - - - - - - - - - - -
set: abc
All subsets:
abc
ab
ac
a
bc
b
c
               // empty set
All subsets with 2 elements:
ab
ac
bc
All permutatons:
abc
acb
bac
bca
cba
cab
- - - - - - - - - - - - - - - - -
set: abcd
All subsets:
abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d
               // empty set
All subsets with 1 element:
a
b
c
d
All subsets with 2 element:
ab
ac
ad
bc
bd
cd
All permutatons:
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc
- - - - - - - - - - - - - - - - -
Consider numbers:  2 3 5
2 sums adding to 5      // 2+3, 5
0 sums adding to 4
- - - - - - - - - - - - - - - - -
Consider numbers:  1 2 3 4 5 6
4 sums adding to 6      // 6, 1+5, 2+4, 1+2+3

General hints:

1.  Everywhere I pass an object to a recursive helping method, I have as a postcondition that all initialized data in the object ends up in the same state it started.  (A similar restriction held in the Queens homework whenever a solution failed and you had to backtrack.)
2.  In multistep problems, the recursive method is generally:  finish the rest of the steps given some number of steps so far.
3.  In each of these problems I am not asking for one successful case, but all cases (or a count of all successful cases).  Hence you not only need to finish the rest, but always finish the rest in all possible ways.
4.  In all the problems that ask you to print, I suggest you completely figure out what is in a solution line first, and then print the whole line.  Find a way to remember what you have so far that is efficient for the particular problem.

All of my recursive methods have under 10 lines of code, but they may be tough to imagine.  If you look at one solution, it might give you some idea how to go about another problem, though the manners in which the recursive calls aid in the larger situation does vary with the context.

How to reduce the problems to simpler ones (Choosing where to start individual solutions)

If you uncover more and more of any one of my solutions, you get more and more hints.  They all have the same structure:

Right after the heading for each method, I have a comment indicating in general how to break the problem into steps.  (All these problems are pretty similar at this level.)

Then after a blank line I have a single line calling my recursive helping method, showing the initial parameters.

Next is the heading of the recursive helping method, possibly adding some meaningful parameter names.

Next is documentation on the helping method -- at this point you are in about the same place as I left you for Queens and the expression evaluation -- seeing the helping method headings and documentation.

Finally there is concise code for the recursive helping method solution.

Then I go on to the next (nonrecursive) method from the skeleton.

complete solution class

The source code listed below is also in the file ListRecursion.java.
The class starts with a repetition of the main testing program:
The individual methods are in the same order as the skeleton given above.

public class ListRecursion {
  public static void main(String[] args) {
    char[] c3 = {'a', 'b', 'c'};
    char[] c4 = {'a', 'b', 'c', 'd'};
    int[] i3 = {2, 3, 5};
    int[] i6 = {1, 2, 3, 4, 5, 6};
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c3);
    System.out.println("All subsets: ");
    subsets(c3);
    System.out.println("All subsets with 2 elements: ");
    subsetsN(c3, 2);
    System.out.println("All permutations: ");
    permute(c3);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c4);
    System.out.println("All subsets: ");
    subsets(c4);
    System.out.println("All subsets with 1 element: ");
    subsetsN(c4, 1);
    System.out.println("All subsets with 2 element: ");
    subsetsN(c4, 2);
    System.out.println("All permutatons: ");
    permute(c4);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i3.length; j++)
      System.out.print(" " + i3[j]);
    System.out.println();
    System.out.println(countSums(i3, 5)  + " sums adding to 5");
    System.out.println(countSums(i3, 4)  + " sums adding to 4");
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i6.length; j++)
      System.out.print(" " + i6[j]);
    System.out.println();
    System.out.println(countSums(i6, 6)  + " sums adding to 6");
  } // end of main

// - - - - - start of method solutions - - - - - - - - -

  // Print all subsets of e, one per line,
  //    assuming all elements of e are distinct.
  public static void subsets(char[] e) {
    // Implement as multistep process:  include or do not include next char.

    subsetsRest(e, new boolean[e.length], 0);
  }

   private static void subsetsRest(char[] e, boolean[] isIn, int iStart) {
    /*
    e is the array of possible characters.
    e[j] is in the set if isIn[j] is true, for each j < iStart.
    isIn[j] is false for each j >= iStart.
    isIn ends in the same state it starts the method.
    The method provides all choices of true and false values for every
    index >= iStart, and prints the result if iStart == e.length.
    */

    if (iStart == e.length) {
      for (int j = 0; j < e.length; j++)
        if(isIn[j]) System.out.print(e[j]);
      System.out.println();
    }
    else {
      isIn[iStart] = true;
      subsetsRest(e, isIn, iStart+1);  // do include e[iStart]
      isIn[iStart] = false; // placing isIn back in its original state
      subsetsRest(e, isIn, iStart+1);  // not include e[iStart]
    }
  }

  // Print all subsets of e with n elements, one subset per line,
  //    assuming all elements of e are distinct, and 0 <= n <= e.length.
  // (This can be derived from previous code, assembling all subsets,
  //   but try to do it more directly.)
  public static void subsetsN(char[] e, int n) {
    // Implement as multistep process:  include or do not include next char.

    subsetsNRest(e, new char[n], 0, 0);
  }

  private static void subsetsNRest(char[] e, char[] sub, int eStart, int subStart) {
    /*
    e is the array of possible characters.
    If eStart == e.length, and subStart < sub.length, return doing nothing.
    If subStart == sub.length, print sub.
    Letters sub[j] are chosen already if j < subStart.
    Fill remaining places in sub with some elements e[k], k >= eStart.
    Returns with sub[j] unchanged if j < eStart.
    */

    if (subStart == sub.length)
      System.out.println(sub);
    else if (eStart < e.length) {
      sub[subStart] = e[eStart];
      subsetsNRest(e, sub, eStart+1, subStart+1); // do add e[eStart]
      subsetsNRest(e, sub, eStart+1, subStart); // do not add e[eStart]
    }
  }

  // Print out the elements of e in all possible orders,
  //    assuming all elements of e are distinct.
  public static void permute(char[] e) {
    // implement as multistep process:
    //   choose element at index i from elements now at index >= i

    permuteRest(e, 0);
  }

  private static void permuteRest(char[] e, int iStart) {
    /*
    e is a possible permutation.
    Keep e[j] in its position if j < iStart.
    Do all permutations for elements e[j], j >= iStart.
    Return with the order of e elements the same as the beginning.
    */

    if (iStart == e.length)
      System.out.println(e);
    else
      for (int j = iStart; j < e.length; j++) {
        swap(e, iStart, j); // helping method next
        permuteRest(e, iStart+1);
        swap(e, iStart, j); // return to original state
      }
  }

  private static void swap(char[] e, int i, int j) {
    char temp = e[i];
    e[i] = e[j];
    e[j] = temp;
  }

  // Return a count of all the sums of subsets of one or more elements from x
  //   that add to sum.  Order does not matter.
  // For simplicity you may assume that all the elements of x are distinct.
  // Again this could be done by assembling all subsets, but do it more directly.
  public static int countSums(int[] x, int sum) {
    // Implement as multistep process:  include next number or not in sum.

    return countSumsRest(x, sum, 0);
  }

  private static int countSumsRest(int[] x, int sumMissing, int iStart) {
    /*
    x is the array of numbers you can add.
    sumMissing is the desired sum from some of the element x[j], j >= iStart.
    */

    if (iStart == x.length) return 0;
    int count = 0;
    count += countSumsRest(x, sumMissing, iStart+1);// sums not using x[iStart]
    sumMissing -= x[iStart];                        // do use x[iStart]
    if (sumMissing == 0) count++;                   // sum ending here?
    count += countSumsRest(x, sumMissing, iStart+1);// longer sums using x[iStart]
    return count;
  }
} // end of ListRecursion