|
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).
|
|
