Practice with Recursion

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, value);
    } else {
      add(current.left, value);
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] { 1, 2, 5, 8, 9 });
    System.out.println(tree);
  }
}

Practice with Recursion
> Click or hit Control-Enter to run Example.main above

I have good news and bad news…

Good news: you did well on Midterm 1!
Good news: we have a fantastic new MP for you to enjoy…
Bad news: it won’t be ready until Monday, but that means…
Good news: you have a weekend off! Enjoy it.
Good news: we still have over a month left together.

In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Each parent has one or more children.

Each parent has one or more children. Each child has one parent.

We refer to the top of the tree as the root.

We refer to the top of the tree as the root. We refer to nodes without any children as leaves.

We can enumerate each level in a tree starting with the root as 0.

The depth or height of a tree is the maximum distance from root to leaf.

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

We can count recursively:

Break the problem into smaller subproblems
Solve the smallest subproblem
Combine the results

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, value);
    } else {
      add(current.left, value);
    }
  }
  public int size() {
    return 0;
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] { 1, 2, 5, 8, 9 });
    System.out.println(tree.size());
    System.out.println(tree);
  }
}

> Click or hit Control-Enter to run Example.main above

Recursion can be hard to wrap your mind around at first. But these three strategies will help.

Know when to stop. When you identify the smallest subproblem, you must return. Otherwise your program will not terminate. This is also called the base case.
Make the problem smaller in each step. If the problem doesn’t get smaller, you will never reach the base case. This is also called the recursive step.
Combine results from your recursive calls properly.

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

Base case: n == 1
Recursive step: decrement n towards 1
Combine results: multiply current n with the result of the next subproblem

int factorial(int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1); // I called myself!
  }
}

You must reach the base case. Otherwise your problem will never stop, run out of memory, and crash.

How can the code above fail to reach the base case?

> Click or hit Control-Enter to run the code above

Recursive solutions can be difficult to understand.

The goal is to write clear code, not use a particular solution technique.
If an iterative solution is more clear, use that.
Sometimes a recursive solution is much more clear.
Don’t use recursion just to be cool.
Don’t use recursion because it is fewer lines of code. Who cares? Clarity is the goal, not brevity.

> Click or hit Control-Enter to run the code above

5 doesn’t have a left child

5 doesn’t have a left child
Add 3 as 5’s left child

5 doesn’t have a right child

5 doesn’t have a right child
Add 10 as 5’s right child

5 has both a right and left child

5 has both a right and left child
Randomly choose a subtree

5 has both a right and left child
Randomly choose a subtree
And call add on that subtree

10 doesn’t have a left child

10 doesn’t have a left child
Add 9 as its left child

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, value);
    } else {
      add(current.left, value);
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
}
public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new Integer[] { 1, 2, 5, 8, 9 });
    System.out.println(tree);
  }
}

> Click or hit Control-Enter to run Example.main above

Let’s find the number of nodes in our tree where the value of the right child is greater than or equal to value of the left child.

Base case: We’ve reached a tree with one node. It does not have a right child or left child, so we can return 0.
Recursive step: Consider our right tree and left tree separately.
Combine results: Determine whether our right child is greater than our left child. If so, add 1 to the sum of results from our left and right child.

import java.util.Random;

public class BinaryTree {
  private static Random random = new Random();
  private class Node {
    private Object value;
    private Node right;
    private Node left;
    Node(Object setValue) {
      value = setValue;
    }
  }
  private Node root;
  BinaryTree(Object[] values) {
    for (Object value : values) {
      add(root, value);
    }
  }
  public void add(Object value) {
    add(root, value);
  }
  private void add(Node current, Object value) {
    if (current == null) {
      root = new Node(value);
    } else if (current.right == null) {
      current.right = new Node(value);
    } else if (current.left == null) {
      current.left = new Node(value);
    } else if (random.nextBoolean()) {
      add(current.right, value);
    } else {
      add(current.left, value);
    }
  }
  public String toString() {
    return toString(root);
  }
  private String toString(Node current) {
    if (current == null) {
      return "";
    }
    return "[" + current.value.toString() + "]" +
      toString(current.right) + toString(current.left);
  }
  public int rightGreaterThanLeft() {
  }
}

public class Example {
  public static void main(String[] unused) {
    BinaryTree tree = new BinaryTree(new int[] { 1, 2, 3, 4 });
    System.out.println(tree.rightGreaterThanLeft());
  }
}

> Click or hit Control-Enter to run Example.main above

This will be our second CS 125 Final Project Fair: bigger and better than ever.

Date: Thursday 12/13/2018, Reading Day
Participation: Optional but worth 1% extra credit
Location: TBD, but probably in the Illinois Union with awards following in Foellinger.

All of you will get a job. Not all of you will get a great 1 job.

Here’s a good strategy for not getting a good job:

Take CS classes.
Do the projects.
Get good grades.
Don’t do any side projects: focus on grades instead.

Show your passion for technology.

The CS 125 Project Fair is intended to get you started doing that.

MP5 will be out Monday morning.
I have office hours today from 10AM–12PM. Please come by!
Note that we will have class on the Friday before Thanksgiving but not on the Wednesday before Thanksgiving. As usual, the calendar is up-to-date.
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!

Good News, Bad News

Trees

Review: Trees: Parent and Child

Review: Trees: Parent and Child

Review: Trees: Root and Leaves

Review: Trees: Root and Leaves

Review: Trees: Level and Depth

Review: Trees: Level and Depth

Review: Trees: Level and Depth

Review: Trees: Level and Depth

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Node Counting

Recursive Strategies

Recursive Factorial

Reaching Base Camp

Recursion v. Iteration

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Add

Recursive Tree Right Greater Than Left

What’s Our (Recursive) Algorithm?

Recursive Tree Right Greater Than Left

Questions About Recursion?

CS 125 Project Fair

Fair Overview

How to Not Get a Great CS Job

How to Get a Great CS Job

Example Spring 2018 Fair Projects

Announcements