ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
List: recursive list processing
by
Marcel Turcotte
Version March 22, 2020
Preamble
Preamble
Overview
Overview
List: recursive list processing
We revisit the concept of recursivity, this time in the context of processing linked lists. We
develop a general strategy, “head & tail”, that can be applied to all the problems covered
in this course.
General objective:
This week, you will be able to design recursive methods for processing linked lists.
1 88
«To iterate is human, to recurse divine»
L. Peter Deutsch
Preamble
Learning objectives
Learning objectives
Recognize the problems for which recursion is appropriate.
Discuss the efficiency of recursive list processing in Java, especially in relation to
memory consumption.
Explain the role of parameters to control the flow of recursive program execution.
Paraphrase the “head & tail” for recursive processing of lists.
Use the “head & tail” strategy to design a recursive method for processing a linked
list.
Readings:
Pages 233-238 of E. Koffman and P. Wolfgang.
3 88
Preamble
Plan
Plan
1 Preamble
2 Theory
3 Implementation
4 Principles
5 Prologue
4 88
Theory
Discussion
What problems have you solved using recursivity?
What do these problems have in common?
5 88
Theory
The solution to a given problem can be constructed from the solutions of the
subproblems;
These sub-problems are of the same nature and therefore can be solved in the
same way;
The sub-problems are getting smaller and smaller (convergence);
Finally, there is a size of problems that can be solved in a trivial way, without
recursive calls, which are the base cases.
6 88
Remarks
Recursivity and iteration are of the same nature.
It is important that the size of the problems to be handled decreases, otherwise
there would be an infinite number of recursive calls (equivalent to the infinite
loop); in practice the program will terminate when all the memory reserved for
method calls is exhausted.
So there has to be a size of problem that can be solved without recursive calls,
in order to stop recursivity.
These are the base cases. There has to be at least one, but there can be more
than one.
The base cases should be processed first in order to stop the recursion, if
necessary.
7 88
Remarks (continued)
The programming languages Lisp, Prolog and Haskell, to name but a few, have no
iterative control statements, iteration is replaced by recursivity.
Compilers automatically transform some forms of recursivity into iteration.
The XSLT Transformations technology used in particular for certain Web
applications is based on the concept of recursivity.
Some treatments of binary search trees will be very simple to express using
recursivity, but very complex otherwise.
8 88
Theory
Pattern
Pattern
t ype method ( pa ramete r s ) {
type r e s u l t ;
i f ( t e s t ) { // base ca se
r e s u l t = c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l
} e l s e { // g e n e r a l ca s e
// pre−p r o c e s s i n g : p a r t i t i o n i n g the data
r e s u l t = method ( sub−problem ) ; // r e c u r s i v e c a l l
// post−p r o c e s s i n g : combine the r e s u l t
}
re tu rn r e s u l t ;
}
9 88
Theory
Factorial
Factorielle
pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) {
i n t s , r e s u l t ;
i f (n<=1) { // base ca se
r e s u l t = 1 ;
} e l s e { // g e n e r a l ca s e
i n t n1 = n−1;
s = f a c t o r i a l ( n1 ) ;
r e s u l t = n ∗ s ;
}
re tu rn r e s u l t ;
}
The above method corresponds to the proposed model:
First we check the base case, its result is calculated without recursive call (recursivity
stops here!);
The general case creates smaller and smaller subproblems.
10 88
Factorial — a terse implementation
pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) {
i f (n<=1) {
re tu rn 1 ;
}
re tu rn n ∗ f a c t o r i a l ( n −1);
}
The statement return returns control to the caller, it stops the execution of the
method, no other statement of this call will be executed.
11 88
Factorial — a terse implementation
pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) {
i f (n<0) {
throw new I l l e g a l A r g u m e n t E x c e p t i o n ( I n t e g e r . t o S t r i n g ( n ) ) ;
}
i f (n<=1) {
re tu rn 1 ;
}
re tu rn n ∗ f a c t o r i a l ( n −1);
}
12 88
Theory : “head & tail”
Let’s establish a general strategy for recursive list processing.
Breaking the list into two parts, the first element (head) and the rest of the list
(tail)∗
∗Here, head and tail are not the instance variables.
13 88
Implementation
Implementation of the class LinkedList
We’ll use a singly linked list.
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e T v a l u e ;
p r i v a t e Node
p r i v a t e Node (T va lue , Node
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;
}
}
p r i v a t e Node
// . . .
}
14 88
Implementation
size
Calculating the size of a list
Let’s first consider calculating the size of a list.
Let current, a variable of type Node, designate an element of the list.
Knowing that the size of the list starting with the element designated by
current.next is n,
what is the size of the list starting with the element designated current?
The size of the list starting with the element designated by current is n+1.
15 88
Calculating the size of a list
The strategy “head & tail” suggests that we start by posing the recursive call,
passing current.next.
i n t n = s i z e ( c u r r e n t . nex t ) ;
What’s the value of n? What does n mean?
This is the length of the list starting with the element designated by current.next.
What is the size of the list starting with the element designated current?
The length of the list starting with the element designated by current is n+1.
16 88
Calculating the size of a list
What’s the shortest valid list and how long is it?
It’s the empty list and its length is 0.
What is the value of current if the list is empty?
The value of current is null.
17 88
Calculating the size of a list
This suggests the following partial implementation:
i n t n ;
i f ( c u r r e n t == nu l l ) {
n = 0 ;
} e l s e {
n = 1 + s i z e ( c u r r e n t . nex t ) ;
}
What is the type of the parameter for the method size?
The type of the parameter is Node.
18 88
Calculating the size of a list
i n t s i z e ( Node
i n t n ;
i f ( c u r r e n t == nu l l ) {
n = 0 ;
} e l s e {
n = 1 + s i z e ( c u r r e n t . nex t ) ;
}
re tu rn n ;
}
19 88
…
i n t s i z e ( Node
i f ( c u r r e n t == n u l l ) {
r e t u r n 0 ;
}
r e t u r n 1 + s i z e ( c u r r e n t . nex t ) ;
}
Remarks
Notice that the method size uses no instance variables!
One controls recursivity using the parameter.
Each call has its own working memory (activation block) and therefore its own copies
of the local variables and parameters.
i n t s i z e ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;
}
re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;
}
The base case is checked out first.
22 88
Calling the method size
How do we use this method to calculate the size of the list starting with the node
designated by head?
i n t s i z e ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;
}
re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;
}
i n t s i z e ( ) {
re tu rn s i z e ( head ) ;
}
23 88
The recursive method is a helper
The first call is initiated by a method of visibility public. The value of head is passed
as a parameter.
pub l i c i n t s i z e ( ) {
re tu rn s i z e ( head ) ;
}
The recursive method must be of visibility private since its parameter is of type
Node.
p r i v a t e i n t s i z e ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;
}
re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;
}
24 88
head
B CA
pub l i c i n t s i z e ( ) {
r e t u r n s i z e ( head ) ;
}
p r i v a t e i n t s i z e ( Node
i f ( c u r r e n t == n u l l ) {
r e t u r n 0 ;
}
r e t u r n 1 + s i z e ( c u r r e n t . nex t ) ;
}
In practice
Each call has its own activation block (working memory) on the call stack, so the
size of the system stack will be proportional to the size of the list.
26 88
Implementation
Summary
Summary
t ype method ( Node
type r e s u l t ;
i f ( c u r r e n t . . . ) { // base ca se
c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l
} e l s e { // g e n e r a l ca s e
// pre−p r o c e s s i n g
s = method ( c u r r e n t . nex t ) ; // r e c u r s i o n
// post−p r o c e s s i n g
}
re tu rn r e s u l t ;
}
27 88
“head & tail”
Steps:
What does method(current.next) mean?
The solution to a problem, smaller by an element.
How are we going to use this result to construct a solution for a list beginning with
the element designated by current?
What are the base cases?
What’s the shortest valid list?
What’s the result?
28 88
Implementation
findMax
LinkedList
Let’s now use a list whose elements have a method compareTo.
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e T v a l u e ;
p r i v a t e Node
p r i v a t e Node (T va lue , Node
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;
}
}
p r i v a t e Node
// . . .
}
29 88
findMax
Let’s apply the strategy as suggested.
r e s u l t = f indMax ( c u r r e n t . nex t ) ;
What’s the value of result? What does result mean?
The largest value for the list beginning with the element designated current.next
What do we do if result is greater than current.value?
i f ( r e s u l t . compareTo ( c u r r e n t . v a l u e ) > 0) {
re tu rn r e s u l t ;
} e l s e {
re tu rn c u r r e n t . v a l u e ;
}
30 88
findMax
This process builds smaller and smaller problems. What’s the shortest valid list?
No, not the empty list, but the list containing only one element.
What’s the returned value going to be?
i f ( c u r r e n t . nex t == nu l l ) {
re tu rn c u r r e n t . v a l u e ;
}
31 88
pub l i c E findMax ( ) {
i f ( head == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
re tu rn f indMax ( head ) ;
}
p r i v a t e E findMax ( Node
i f ( c u r r e n t . nex t == nu l l ) {
re tu rn c u r r e n t . v a l u e ;
}
E r e s u l t = findMax ( c u r r e n t . nex t ) ;
i f ( r e s u l t . compareTo ( c u r r e n t . v a l u e ) > 0) {
re tu rn r e s u l t ;
} e l s e {
re tu rn c u r r e n t . v a l u e ;
}
}
head
B CA
p r i v a t e E findMax ( Node
i f ( p . nex t == n u l l ) {
r e t u r n p . v a l u e ;
}
E r = findMax ( p . nex t ) ;
i f ( r . compareTo ( p . v a l u e ) > 0) {
r e t u r n r ; ‘
} e l s e {
r e t u r n p . v a l u e ;
}
}
Each of the following examples
introduces a new problematic.
Implementation
E get(int index)
E get(int index)
The method E get(int index) returns the element at the specified value (index) of
the list.
What was the strategy adopted for the non-recursive method?
It was necessary to count the number of visited nodes and to stop the execution of the
loop while after having visited index nodes.
For a recursive method, how do we determine the number of nodes visited?
We could add a parameter to count the number of nodes visited. Initially 0, then 1, 2,
etc.
35 88
Study the following partial implementation:
pub l i c E get ( i n t i n d e x ) {
re tu rn get ( head , i n d e x ) ;
}
p r i v a t e E get ( Node
. . .
}
If index represents the position of the element in relation to the list starting at
position current, what is the position of the element in relation to the list starting at
position current.next?
That’s right, index-1.
What will the method do if the value of the index is 0?
It must return current.value.
No recursive call is made.
That’s the base case.
E get(int index)
p r i v a t e E get ( Node
i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;
}
re tu rn get ( c u r r e n t . next , index −1);
}
What would happen if the initial value of the index was greater than the total
number of items on the list?
index > 0 and current == null
37 88
E get(int index)
p r i v a t e E get ( Node
i f ( c u r r e n t == nu l l ) {
throw new IndexOutOfBoundsExcept ion ( ) ;
}
i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;
}
re tu rn get ( c u r r e n t . next , index −1);
}
38 88
pub l i c E get ( i n t i n d e x ) {
i f ( i n d e x < 0) {
throw new IndexOutOfBoundsExcept ion ( ) ;
}
re tu rn get ( head , i n d e x ) ;
}
p r i v a t e E get ( Node
i f ( c u r r e n t == nu l l ) {
throw new IndexOutOfBoundsExcept ion ( ) ;
}
i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;
}
re tu rn get ( c u r r e n t . next , index −1);
}
head
B CA
p r i v a t e E get ( Node
i f ( i n d e x == 0) {
r e t u r n p . v a l u e ;
}
r e t u r n get ( p . next , index −1);
}
Implementation
int indexOf(E element)
int indexOf(E element)
The method indexOf returns the position of the leftmost occurrence of the element
in this list, and −1 if the value is not found there.
The numbering of the elements starts at zero.
41 88
int indexOf(E element)
According to the “head & tail” strategy, the general case will involve a recursive call
such as this:
s = indexOf ( c u r r e n t . next , e l ement ) ;
What does the value of s represent?
It’s the position of the element in the list designated by current.next.
Compared to the current list, the one designated by current, what is the position of
element?
s + 1
42 88
int indexOf(E element)
If the value of s is greater or equal to zero, s is the position of the element in
the rest of list.
What does s == -1 mean?
The element was absent from the rest of the list.
Which case hasn’t been dealt with?
current.value.equals(element)
What value should we return then?
0
43 88
int indexOf(E element)
s = indexOf ( c u r r e n t . next , e l ement ) ;
i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
r e s u l t = 0 ;
} e l s e i f ( s == −1) {
r e s u l t = s ;
} e l s e {
r e s u l t = 1 + s ;
}
44 88
int indexOf(E element)
What’s the base case?
The shortest list is the empty list, it doesn’t contain the element you’re looking for,
just return the special value -1.
i f ( c u r r e n t == nu l l ) {
re tu rn −1;
}
45 88
int indexOf(E element)
p r i v a t e i n t i ndexOf ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn −1;
}
i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;
i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
re tu rn 0 ;
}
i f ( r e s u l t == −1) {
re tu rn r e s u l t ;
}
re tu rn r e s u l t + 1 ;
}
46 88
int indexOf(E element)
Is it working?
Yes.
There’s still a problem with that implementation.
What is it?
47 88
head
i n t i ndexOf ( Node
i f ( p == n u l l ) r e t u r n −1;
i n t r = indexOf ( p . next , e ) ;
i f ( p . v a l u e . e q u a l s ( e ) ) r e t u r n 0 ;
i f ( r == −1) r e t u r n r ;
r e t u r n r + 1 ;
}
int indexOf(E element)
How do we stop recursive calls as soon as the value we’re looking for is found?
p r i v a t e i n t i ndexOf ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn −1;
}
i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;
i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
re tu rn 0 ;
}
i f ( r e s u l t == −1) {
re tu rn r e s u l t ;
}
re tu rn r e s u l t + 1 ;
}
49 88
int indexOf(E element)
p r i v a t e i n t i ndexOf ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn −1;
}
i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
re tu rn 0 ;
}
i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;
i f ( r e s u l t == −1) {
re tu rn r e s u l t ;
}
re tu rn r e s u l t + 1 ;
}
50 88
Implementation
E indexOfLast(E element)
E indexOfLast(E element)
The method indexOfLast returns the position of the last (rightmost) occurrence of
the element, and -1 otherwise.
What are the changes to be made?
Can current.value.equals(element) be part of the base case?
No, recursion must go through the entire list.
How to process the result indexOfLast(current.next, element)?
51 88
pub l i c i n t i n dexOfLa s t (E e lement ) {
re tu rn i n dexOfLa s t ( head , e l ement ) ;
}
p r i v a t e i n t i n dexOfLa s t ( Node
i f ( c u r r e n t == nu l l ) {
re tu rn −1;
}
i n t r e s u l t = indexOfLa s t ( c u r r e n t . next , e l ement ) ;
i f ( r e s u l t > −1) {
re tu rn r e s u l t + 1 ;
} e l s e i f ( e l ement . e q u a l s ( c u r r e n t . v a l u e ) ) {
re tu rn 0 ;
}
re tu rn −1;
}
Implementation
boolean contains(E element)
Exercise
boolean contains(E element)
53 88
Implementation
boolean isIncreasing()
boolean isIncreasing()
The methods size, indexOf and contains only deal with one element at a time.
Let’s consider a recursive implementation of the method isIncreasing.
Examine each consecutive pair and return the value false as soon as a pair is not
increasing.
If the method attains the end of the list then the list is ascending!
54 88
boolean isIncreasing()
pub l i c boolean i s I n c r e a s i n g ( ) {
re tu rn i s I n c r e a s i n g ( head ) ;
}
55 88
boolean isIncreasing()
What’s the base case?
What’s the shortest valid list?
The empty list and the singleton are growing.
i f ( ( c u r r e n t == nu l l ) | | ( c u r r e n t . nex t == nu l l ) ) {
re tu rn t rue ;
}
56 88
boolean isIncreasing()
General case.
Which approach is preferable?
1. Do a recursive call, then process the result.
2. Process the current position, then do a recursive recursive call.
i f ( c u r r e n t . v a l u e . compareTo ( c u r r e n t . nex t . v a l u e ) > 0) {
re tu rn f a l s e ;
} e l s e {
re tu rn i s I n c r e a s i n g ( c u r r e n t . nex t ) ;
}
57 88
boolean isIncreasing()
p r i v a t e boolean i s I n c r e a s i n g ( Node
i f ( ( c u r r e n t == nu l l ) | | ( c u r r e n t . nex t == nu l l ) ) {
re tu rn t rue ;
}
i f ( c u r r e n t . v a l u e . compareTo ( c u r r e n t . nex t . v a l u e ) > 0 ) {
re tu rn f a l s e ;
}
re tu rn i s I n c r e a s i n g ( c u r r e n t . nex t ) ;
}
58 88
Implementation
Exercises
Exercices
void addLast(E element)
boolean equals(LinkedList
59 88
Implementation
void remove(E element)
void remove(E element)
We’re now considering methods that transform the structure of the list.
For the methods indexOf and contains, the main consequence of additional
recursive calls is the inefficiency of the method.
On the other hand, recursive methods that transform lists can lead to more serious
problems.
Consider the example of the method remove, which removes the first occurrence of
an object in the list.
60 88
void remove(E element)
Give the the high-level strategy.
Traverse the list.
Find the element.
Remove the element.
61 88
public void remove(E element)
What will be the difficulties?
We’ll remember that when traversing a singly linked list using a while loop, we had to
stop one position before the element to be removed, since it’s the variable next of the
preceding element that has to be modified.
To remove the first element, we must modify the variable head of the header, and not
the variable next of the preceding node.
62 88
public void remove(E element)
What are the preconditions?
element != null
The list is not empty.
What are the special cases?
The element being sought is in first position.
63 88
public void remove(E element)
pub l i c vo id remove (E e lement ) {
i f ( e l ement == nu l l ) {
throw new N u l l P o i n t e r E x c e p t i o n ( ” I l l e g a l argument ” ) ;
}
i f ( head == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
i f ( head . v a l u e . e q u a l s ( e l ement ) ) {
head = head . nex t ;
} e l s e {
remove ( head , e l ement ) ;
}
}
64 88
Remarks
For the first call to the method remove(Node
that current.value.equals(element) is false. Why?
It’s the first call, current == head.
If head.value.equals(element) were true at the time of the call to the public method,
then there would have been no call to the private method.
The recursive method will preserve this property, it checks if the sought element,
element, is at the position that follows, current.next, and if yes, removes this node
and finishes, otherwise it continues its search.
65 88
remove(Node
General case: Which scenario seems the most appropriate:
1. Do a recursive call, followed by a post-processing?
2. Do a pre-processing, followed by a recursive call (if necessary)?
Since we have to remove the leftmost element, should we do a pre-processing followed
by a recursive call (if necessary)? (Strategy 2)
66 88
remove(Node
What’s the necessary pre-processing?
If current.next.value.equals(element), remove the next element.
Otherwise, process the rest of the list (recursive call).
67 88
remove(Node
What’s the base case?
Singleton.
What do we do now?
Throw the exception NoSuchElementException.
68 88
remove(Node
p r i v a t e vo id remove ( Node
i f ( c u r r e n t . nex t == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
i f ( c u r r e n t . nex t . v a l u e . e q u a l s ( e l ement ) ) {
c u r r e n t . nex t = c u r r e n t . nex t . nex t ; // base ca se
} e l s e {
remove ( c u r r e n t . next , e l ement ) ; // g e n e r a l ca s e
}
}
69 88
pub l i c vo id remove (E e lement ) {
i f ( e l ement == n u l l ) {
throw new N u l l P o i n t e r E x c e p t i o n ( ” I l l e g a l argument ” ) ;
}
i f ( head == n u l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
i f ( head . v a l u e . e q u a l s ( e l ement ) ) {
head = head . nex t ; // s p e c i a l c a s e
} e l s e {
remove ( head , e l ement ) ;
}
}
p r i v a t e vo id remove ( Node
i f ( c u r r e n t . nex t == n u l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
i f ( c u r r e n t . nex t . v a l u e . e q u a l s ( e l ement ) ) {
c u r r e n t . nex t = c u r r e n t . nex t . nex t ; // base ca se
} e l s e {
remove ( c u r r e n t . next , e l ement ) ; // g e n e r a l ca s e
}
}
Exercises
void removeLast()
void removeLast(E element)
void removeAll(E element)
void remove(int pos)
71 88
Implementation
LinkedList
LinkedList
toIndex)
The method will return a new list containing the elements located between the
positions fromIndex and toIndex of the original list, without changing it.
72 88
Discussion
Propose a strategy to build the resulting list.
1. Post-processing
Traverse the list to the highest index;
Return a list containing only the value at that position;
Add the current element to the start of the list, if its position is within the range.
2. Pre-processing
An empty list is passed as a parameter to the first call;
Add the current element to the end of the list, if the current position is part of the
interval;
Recusive call.
73 88
Strategy 1
Recursive calls traverse the list from left to right, recursion stops when the index
toIndex is reached.
Base Case:
L i n k e d L i s t
i f ( i n d e x == t o I n d e x ) {
r e s u l t = new L i n k e d L i s t
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;
}
74 88
Strategy 1
General case:
r e s u l t = s u b L i s t ( c u r r e n t . next , i n d e x +1, f romIndex , t o I n d e x ) ;
What does result contain?
What’s the next step?
i f ( i n d e x > f romIndex ) {
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;
}
75 88
pub l i c L i n k e d L i s t
r e t u r n s u b L i s t ( head , 0 , f romIndex , t o I n d e x ) ;
}
p r i v a t e L i n k e d L i s t
L i n k e d L i s t
i f ( i n d e x == t o I n d e x ) {
r e s u l t = new L i n k e d L i s t
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;
} e l s e {
r e s u l t = s u b L i s t ( c u r r e n t . next , i n d e x +1, f romIndex , t o I n d e x ) ;
i f ( i n d e x >= fromIndex ) {
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;
}
}
r e t u r n r e s u l t ;
}
The handling of the preconditions (range of illegal values) is left as exercise.
Strategy 2
For the second strategy, the list of results is created at the outset and elements
are inserted while traversing the list.
pub l i c L i n k e d L i s t
L i n k e d L i s t r e s u l t = new L i n k e d L i s t
s u b L i s t ( head , 0 , r e s u l t , f romIndex , t o I n d e x ) ;
r e t u r n r e s u l t ;
}
77 88
Strategy 2
Base Case:
i f ( i n d e x == t o I n d e x ) {
r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
}
result.addLast(current.value) ou result.addFirst(current.value)?
78 88
Strategy 2
General case:
i f ( i n d e x >= fromIndex ) {
r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
}
s u b L i s t ( c u r r e n t . next , i n d e x +1, r e s u l t , f romIndex , t o I n d e x ) ;
result.addLast(current.value) ou result.addFirst(current.value)?
79 88
pub l i c L i n k e d L i s t
L i n k e d L i s t r e s u l t = new L i n k e d L i s t
s u b L i s t ( head , 0 , r e s u l t , f romIndex , t o I n d e x ) ;
r e t u r n r e s u l t ;
}
p r i v a t e vo id s u b L i s t ( Node
i n t f romIndex , i n t t o I n d e x ) {
i f ( i n d e x == t o I n d e x ) {
r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
} e l s e {
i f ( i n d e x >= fromIndex ) {
r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
}
s u b L i s t ( c u r r e n t . next , i n d e x +1, r e s u l t , f romIndex , t o I n d e x ) ;
}
}
Principles
Principles
Parameters play an essential role when writing recursive methods.
A parameter of type Node, current, plays a key role in controlling the execution
of the method.
Sample tests for the base case:
current == null
current.next == null
current.value.equals(element)
current.next.value.equals(element)
General case:
The value of current.next is passed as a parameter for the recursive call in order to
process the rest of the list.
81 88
Principles
There are two mechanisms for passing information between calls.
1. Parameters:
A counter: If each call must know its position in the list, the value of a counter is
passed as a parameter, and each call passes to the value plus one.
We could also decrement the value with each call.
2. Return value:
The method size returns the size of the list from the element designated by its
parameter current.
For the caller, the size of the list is one more than the returned value.
82 88
t ype method ( Node
type r e s u l t ;
i f ( c u r r e n t . . . ) { // base ca se
c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l
} e l s e { // g e n e r a l ca s e
// pre−p r o c e s s i n g
s = method ( c u r r e n t . nex t ) ; // r e c u r s i o n
// post−p r o c e s s i n g
}
re tu rn r e s u l t ;
}
«head & tail»
Steps:
What does method(current.next) mean?
The solution to a problem, smaller by an element.
How are we going to use this result to construct a solution for a list beginning with
the current element?
What are the base cases?
What’s the shortest valid list?
What’s the result?
84 88
Prologue
Summary
We proposed the “head & tail” strategy
Base case: usually a test involving the value of current.
General case: recursive call passing the value of current.next as a parameter.
We control recursivity using the parameters.
85 88
Next module
Binary Research Trees: concept
86 88
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
87 88
Marcel Turcotte
Marcel.
School of Electrical Engineering and Computer Science (EECS)
University of Ottawa
88 / 88
Marcel.
Preamble
Overview
Learning objectives
Plan
Theory
Pattern
Factorial
Implementation
size
Summary
findMax
E get(int index)
int indexOf(E element)
E indexOfLast(E element)
boolean contains(E element)
boolean isIncreasing()
Exercises
void remove(E element)
LinkedList
Principles
Prologue