1.
   public static int sum(int n) {
       if (n == 1)
            return 1;
       else
            return n + sum(n-1);
   }

2.
   public static int count(String s, char c) {
       if (s.equals("")) return 0;
       else if (s.charAt(0)==c)
           return 1 + count(s.substring(1),c);
       else
           return count(s.substring(1),c);
   }

3.
   public void printInReverse() {
       if (head == null)
           System.out.println();
       else
           printInReverse(head);
   }

   private void printInReverse(Node<E> nodePtr) {
       if (nodePtr == null)
           return; 
       printInReverse(nodePtr.next);
       System.out.println(nodePtr.data);
   }  

4.
   public static ArrayList<String> makePermutations(String s) {
       ArrayList<String> perms = new ArrayList<String>();
       if (s.length() == 1) {
           perms.add(s);
           return perms;
       }
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           String remaining = s.substring(0,i) + s.substring(i+1);
           ArrayList<String> subperms = makePermutations(remaining);
           for (String sp: subperms)
                perms.add(c + sp);
       }
       return perms;
   }