CSC300 / CSC402: Linked Mutators using Recursion (Optional)

Contents [0/5]

Loop [1/5]
Non-Nullable Recursion [2/5]
Non-Nullable Recursion [3/5]
Nullable Recursion [4/5]
Nullable Recursion [5/5]

(Click here for one slide per page)


Loop [1/5]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  public void insert (double item) {  
    if (first == null || first.item >= item) {
      first = new Node (item, first);
    } else {
      Node x = first;



      while (x.next != null && x.next.item < item) {
        x = x.next;
      }
      x.next = new Node (item, x.next);
    }
  }
 insertI-

Non-Nullable Recursion [2/5]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  public void insert (double item) {  
    if (first == null || first.item >= item) {
      first = new Node (item, first);
    } else {
      insertH (first, item);
    }
  }
  private static void insertH (Node x, double item) { 
    if (x.next != null && x.next.item < item) {
      insertH (x.next, item);
    } else {
      x.next = new Node (item, x.next);
    }
  }

Direct translation of loop.

insertRNNF-First-

Non-Nullable Recursion [3/5]

It's more typical to check base case first in a recursive function.

Note that lines 12-13 and 19-20 look almost exactly the same!

The only difference is we're working with first in the starter function and x.next in the helper function.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  public void insert (double item) {  
    if (first == null || first.item >= item) {
      first = new Node (item, first);
    } else {
      insertH (first, item);
    }
  }
  private static void insertH (Node x, double item) { 
    if (x.next == null || x.next.item >= item) {
      x.next = new Node (item, x.next);
    } else {
      insertH (x.next, item);
    }
  }

Computes forwards

A single function call both:

  • creates the new node
  • puts it in its place
insertRNNF-

Nullable Recursion [4/5]

We can get rid of the similar if check in the starter function by using nullable recursion!

  • Recall that recursion is more general than loops.
  • We can change our helper function to return a Node.
  • The calling function then ensures the returned node is put in its place!
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
  public void insert (double item) {  



    first = insertH (first, item);

  }
  private static Node insertH (Node x, double item) { 
    if (x == null || x.item >= item) {
      return new Node (item, x);
    } else {
      x.next = insertH (x.next, item);
      return x;
    }
  }

Computes both forwards and backwards

Two separate function calls

  • the sender makes the new node
  • the receiver puts it in it's place

The receiver could be a call to the starter, or the helper

  • Only check the termination condition once!

This pattern is really great with balanced trees (next quarter).

insertRNF-First-

Nullable Recursion [5/5]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
  public void insert (double item) {  



    first = insertH (first, item);

  }
  private static Node insertH (Node x, double item) { 
    if (x == null || x.item >= item) {
      return new Node (item, x);
    } else {
      x.next = insertH (x.next, item);
      return x;
    }
  }

Easiest to write, once you understand it.

We don't know if a new node will be created in the helper!

Therefore, it's important that the helper function return something back to its caller, and the caller always update the appropriate pointer.

Even if a pointer ends up not being changed, the caller doesn't know if it needs to be changed, so it must unconditionally do the assigment of the pointer!

Some common mistakes:

  • Forget to update first in the starter.
  • Forget to update x.next in the helper.
  • Forget to return x in the helper.
insertRNF-