teaching machines

CS 245 Lecture 11 – Recursion

February 25, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• name that complexity
• recursion
  • char multiplication
  • concentric circles
  • find file
  • file explorer
  • binary search
  • brute force password cracking
  • tournament bracket drawing
  • terrain generation

TODO

• Write a recursive method isOdd that has base cases for 0 and 1 and a general case for all other positive numbers. 1/4 sheet.

Name That Complexity

Code

CharacterMultiplication.java

package lecture11;

public class CharacterMultiplication {
  public static void main(String[] args) {
    System.out.println(multiply('p', 3));
  }

  public static String multiply(char c, int n) {
    String s = null;
    if (n <= 0) {
      s = "";
    } else {
      s = c + "";
      s += multiply(c, n - 1);
    }
    return s;
  }
}

BruteCrack.java

package lecture11;

public class BruteCrack {
  public static void main(String[] args) {
    printPasswords("", 4);
  }

  public static void printPasswords(String prefix,
                                    int n) {
    if (n == 0) {
      System.out.println(prefix);
    } else {
      // n is > 0, so we have more characters to add
      for (char c = 'a'; c <= 'z'; ++c) {
        printPasswords(prefix + c, n - 1);
      }
      // printPasswords(prefix + 'a', n - 1);
      // printPasswords(prefix + 'b', n - 1);
      // printPasswords(prefix + 'c', n - 1);
    }
  }
}

FileExplorer.java

package lecture11;

import java.io.File;
import javax.swing.JFrame;
import javax.swing.JTree;
import javax.swing.tree.DefaultMutableTreeNode;

public class FileExplorer extends JFrame {

  public FileExplorer() {
    DefaultMutableTreeNode root = getNode(new File("/Users/johnch/Things"));
    
    JTree tree = new JTree(root);
    add(tree);
    
    setDefaultCloseOperation(EXIT_ON_CLOSE);
    setSize(512, 512);
    setVisible(true);
  }
  
  private DefaultMutableTreeNode getNode(File file) {
    DefaultMutableTreeNode node = new DefaultMutableTreeNode(file.getName());
    File[] kiddos = file.listFiles();
    if (kiddos != null) {
      for (File kiddo : kiddos) {
        node.add(getNode(kiddo));
      }
    }
    return node;
  }
  
  public static void main(String[] args) {
    new FileExplorer();
  }
}

Haiku