Make recursive methods from an regular method

Question

I have code below that does exactly what I want the program to do. The only problem is I don't even know where to get started to make the methods recursive. I understand using recursion for factorials and other problems but this one is over my head a bit. Can anyone help point me in the right direction?

import java.util.LinkedHashSet;

public class Power_Set{
  public static void main(String[] args) {
    //construct the set S = {a,b,c}
    String set[] = {"a", "b", "c"};

    //form the power set
    LinkedHashSet myPowerSet = powerset(set);

    //display the power set
    System.out.println(myPowerSet.toString());
  }

  /**
   * Returns the power set from the given set by using a binary counter
   * Example: S = {a,b,c}
   * P(S) = {[], [c], [b], [b, c], [a], [a, c], [a, b], [a, b, c]}
   * @param set String[]
   * @return LinkedHashSet
   */
  private static LinkedHashSet powerset(String[] set) {
    //create the empty power set
    LinkedHashSet power = new LinkedHashSet();

    //get the number of elements in the set
    int elements = set.length;

    //the number of members of a power set is 2^n
    int powerElements = (int) Math.pow(2,elements);

    //run a binary counter for the number of power elements
    for (int i = 0; i < powerElements; i++) {        
      //convert the binary number to a string containing n digits
      String binary = intToBinary(i, elements);

      //create a new set
      LinkedHashSet innerSet = new LinkedHashSet();

      //convert each digit in the current binary number to the corresponding     element
      //in the given set
      for (int j = 0; j < binary.length(); j++) {
        if (binary.charAt(j) == '1')
          innerSet.add(set[j]);
        }

        //add the new set to the power set
        power.add(innerSet);
      }

      return power;
    }

    /**
     * Converts the given integer to a String representing a binary number
     * with the specified number of digits
     * For example when using 4 digits the binary 1 is 0001
     * @param binary int
     * @param digits int
     * @return String
     */
    private static String intToBinary(int binary, int digits) {
      String temp = Integer.toBinaryString(binary);
      int foundDigits = temp.length();
      String returner = temp;
      for (int i = foundDigits; i < digits; i++) {
        returner = "0" + returner;
      }
      return returner;
    }
 }

Answer 1

First, let's understand what a power set is. According to wikipedia:

A power set ... is the set of all subsets of S, including the empty set and S itself.

With recursion, we care about two things: the "Base Case" and the "N+1 Case". In regards to a Power Set, the base case is a set containing the empty set:

f({}) => {{}} 

The N+1 case assumes that you already have the power set of N (f(N)), and are merely looking at the difference between that powerset and the one where you add a single element to N. Why is this important? Well, because the idea behind recursion is to solve progressively simpler problems until you reach your base case. This step will be the same for every n above your base case:

f({a}) => {{a},{}}
  + b  => {{a,b}, {a}, {b}, {}}

So what is the difference between these two sets? Well, for each element in the original set, we've both taken that element AND added b to that element. (N.B. each 'element' here is a set.)

Lets do this in pseudo code:

 function addElement(someSet, newElement)
   for each element in someSet              // {a} and {} in the example
     add newElement to that set             // should return {{a,b},{b}}
   take the new set of sets and add someSet // add in {a} and {} (someSet, the original set)

Writing your full function is now a matter of invoking this for each member of your original set. This is where your base and N+1 cases come in:

 function powerSet(originalSet)
   if originalSet is empty, return a set of the empty set  // {{}}  (VERY important it is a set of sets!)
   else
     get the powerSet of the originalSet minus one element //this is the recursive call
     call addElement on that result and the element you took away
     return this result

I leave converting this to code to you, but it should be pretty straightforward.