More Practice with Recursion

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}
public class LinkedList {
  private Item start;
  public LinkedList(int[] array) {
    for (int i = 0; i < array.length; i++) {
      this.addToEnd(array[i]);
    }
  }
  public void addToEnd(int value) {
    Item item = new Item(value, null);
    if (start == null) {
      start = item;
      return;
    }
    Item current;
    for (current = start; current.next != null; current = current.next);
    current.next = item;
  }
  public String toString() {
    String string = "";
    Item current = start;
    while (current != null) {
      string += current.value + " ";
      current = current.next;
    }
    return string.trim();
  }
  public void reverse() {
    if (start != null) {
      start = start.reverse();
    }
  }
}
public class Example {
  public static void main(String[] unused) {
    LinkedList myList = new LinkedList(new int[] { 1, 2, 3 });
    System.out.println(myList);
  }
}

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

Let’s print only leaf nodes: those that have neither a left nor a right child.

Base case: We’ve reached a tree with no left or right node. It’s also a a leaf node, so print our value.
Recursive step: Consider our right tree and left tree separately.
Combine results: Nothing to do here, just continue down the tree.

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

Let’s determine whether a tree contains a certain value.

Base case: We’ve reached a node with no descendants. Return true if its value matches, zero otherwise.
Recursive step: Consider our right tree and left tree separately.
Combine results: Return true if either we or our right or left subtree contain the search value.

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

Every sub(blank) of a (blank) is, itself, a (blank).

Tree
(Contiguous) List
(Contiguous) Array

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}

Just like with trees, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into the current item and the rest of the list.
What’s the smallest subproblem? A list with a single element.

Given a linked list, reverse the elements in the list.

Base case: We’ve reached a list with one element. No need to do anything, since it’s the same reversed.
Recursive step: Consider the current element and the rest of the list separately.
Combine results: Add the current element as the last element of the reversal of the rest of the list.

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}
public class LinkedList {
  private Item start;
  public LinkedList(int[] array) {
    for (int i = 0; i < array.length; i++) {
      this.addToEnd(array[i]);
    }
  }
  public void addToEnd(int value) {
    Item item = new Item(value, null);
    if (start == null) {
      start = item;
      return;
    }
    Item current;
    for (current = start; current.next != null; current = current.next);
    current.next = item;
  }
  public String toString() {
    String string = "";
    Item current = start;
    while (current != null) {
      string += current.value + " ";
      current = current.next;
    }
    return string.trim();
  }
  public void reverse() {
    if (start != null) {
      start = start.reverse();
    }
  }
}
public class Example {
  public static void main(String[] unused) {
    LinkedList myList = new LinkedList(new int[] { 1, 2, 3 });
    System.out.println(myList);
  }
}

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

// Set ourselves as the end of the list
next.next = this;

// Mark that the item after us is null
this.next = null;

At this point we’ve reversed the end of the list.
But Item6 still has a reference to what was its next element, but is now the end of the rest of the list.
So we can use that to set it as the last item.

Just use a loop.

public class Item {
  public int value;
  public Item next;
  Item(int setValue, Item setNext) {
    this.value = setValue;
    this.next = setNext;
  }
}
public class LinkedList {
  private Item start;
  public LinkedList(int[] array) {
    for (int i = 0; i < array.length; i++) {
      this.addToEnd(array[i]);
    }
  }
  public void addToEnd(int value) {
    Item item = new Item(value, null);
    if (start == null) {
      start = item;
      return;
    }
    Item current;
    for (current = start; current.next != null; current = current.next);
    current.next = item;
  }
  public String toString() {
    String string = "";
    Item current = start;
    while (current != null) {
      string += current.value + " ";
      current = current.next;
    }
    return string.trim();
  }
  public void reverse() {
    if (start == null) {
      return;
    }
    Item previous = null;
    Item current = start;
    while (current != null) {
      // Save next since we are about to overwrite it
      Item next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    start = previous;
    return;
  }
}
public class Example {
  public static void main(String[] unused) {
    LinkedList myList = new LinkedList(new int[] { 1, 2, 3 });
    System.out.println(myList);
    myList.reverse();
    System.out.println(myList);
  }
}

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

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

1	10	5	6	4	11	7	-1

1

10

5

6

4

11

7

-1

Each contiguous subarray of an array is, itself, an array.

Just like with trees and lists, we need a way to both make the problem smaller and identify the smallest subproblem.

How do we make the problem smaller? Break the list into two smaller subarrays.
What’s the smallest subproblem? An array with a single item.

Starting with tomorrow’s lab we’re going to introduce you to Android programming in Java with a focus on using external APIs.

Why Android? It’s the best way to build high-impact things using Java.
Why external APIs? It’s the best way to build high-impact things quickly using any language.

We will no longer hold a three-hour seated exam in Foellinger Auditorium on 5/11/2018.

Instead, we will hold a rolling exam in the CBTF from Sunday 5/6/2018–Wednesday 5/9/2018.

The TAs 1 and I have decided together that a computerized exam will be fairer and both faster and easier to grade.
The exam will consist of a mixture of (autograded) programming questions, (autograded) multiple-choice questions, and TA-graded free answer questions.
If you changed your travel plans to stay for the Friday exam, I apologize.

The CBTF final exam will include programming questions.

The editing interface will be familiar to you from the lecture examples.
The grading interface will be familiar to you from the MPs.
We will be rolling this out as soon as possible. At minimum you’ll have a few chances to practice on the last few quizzes leading up to the exam.

The MP5 deadline is today at 5PM.
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
My office hours continue today at 11AM in the lounge outside of Siebel 0226.

Recursive Tree Print Leaves

What’s Our (Recursive) Algorithm?

Recursive Tree Print Leaves

Recursive Tree Search

What’s Our (Recursive) Algorithm?

Recursive Tree Search

How Could We Make This Search More Efficient?

Other Recursive Data Structures

List Recursion

List Recursion

List Recursion

List Recursion

List Recursion

List Recursion

Linked List Reversal

What’s Our (Recursive) Algorithm?

Linked List Reversal

This Is Tricky

Recursive List Reversal

But Don’t Recurse on Lists

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

Array Recursion

We’ll Return to Array Recursion

Rest of the Semester…​

Android Programming (MP6, MP7, Final Project)

Exam Announcement

CBTF Programming Questions

Announcements

Rest of the Semester…