Recursion
EECS2030: Advanced Object Oriented Programming Fall 2017
CHEN-WEI WANG
Recursion: Principle
● is useful in expressing solutions to problems that can be defined:
○ Base Cases: Small problem instances immediately solvable. ○ Recursive Cases:
Large problem instances not immediately solvable.
Solve by reusing solution(s) to strictly smaller problem instances.
● Similar idea learnt in high school: [ mathematical induction ] ● Recursion can be easily expressed programmatically in Java:
○ In the body of a method m, there might be a call or calls to m itself . ○ Each such self-call is said to be a recursive call .
○ Inside the execution of m(i), a recursive call m(j) must be that j < i.
Recursion
recursively
2 of 40
m
(i) { ...
m (j);/* recursive call with strictly smaller value */ ...
}
Recursion: Factorial (1)
● Recall the formal definition of calculating the n factorial:
⎧
⎪1 if n = 0 n! = ⎨
⎪n⋅(n−1)⋅(n−2)⋅⋅⋅⋅⋅3⋅2⋅1 ifn≥1 ⎩
● How do you define the same problem recursively?
⎧
⎪1 if n = 0 n! = ⎨
int (int n) {
int result;
if(n == 0) { /* base case */ result = 1; } else { /* recursive case */
result = n * factorial (n - 1); }
return result; }
factorial
⎪n⋅(n−1)! ifn≥1 ⎩
● To solve n!, we combine n and the solution to (n - 1)!.
3 of 40
Recursion: Factorial (2)
return 5 ∗ 24 = 120
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
return 4 ∗ 6 = 24
return 3 ∗ 2 = 6
return 2 ∗ 1 = 2
return 1 ∗ 1 = 1
return 1
4 of 40
Recursion: Factorial (3)
○ When running factorial(5), a recursive call factorial(4) is made. Call to factorial(5) suspended until factorial(4) returns a value.
○ When running factorial(4), a recursive call factorial(3) is made. Call to factorial(4) suspended until factorial(3) returns a value. ...
○ factorial(0) returns 1 back to suspended call factorial(1).
○ factorial(1) receives 1 from factorial(0), multiplies 1 to it, and
returns 1 back to the suspended call factorial(2).
○ factorial(2) receives 1 from factorial(1), multiplies 2 to it, and
returns 2 back to the suspended call factorial(3).
○ factorial(3) receives 2 from factorial(1), multiplies 3 to it, and
returns 6 back to the suspended call factorial(4).
○ factorial(4) receives 6 from factorial(3), multiplies 4 to it, and
returns 24 back to the suspended call factorial(5).
○ factorial(5) receives 24 from factorial(4), multiplies 5 to it, and
returns 120 as the result.
5 of 40
Recursion: Factorial (4)
● When the execution of a method (e.g., factorial(5)) leads to a nested method call (e.g., factorial(4)):
○ The execution of the current method (i.e., factorial(5)) is suspended, and a structure known as an activation record or
activation frame is created to store information about the progress of that method (e.g., values of parameters and local variables).
○ The nested methods (e.g., factorial(4)) may call other nested methods (factorial(3)).
○ When all nested methods complete, the activation frame of the latest suspended method is re-activated, then continue its execution.
● What kind of data structure does this activation-suspension process correspond to? [ LIFO Stack ]
6 of 40
Tracing Recursion using a Stack
● When a method is called, it is activated (and becomes active) and pushed onto the stack.
● When the body of a method makes a (helper) method call, that (helper) method is activated (and becomes active) and
pushed ontothestack.
⇒ The stack contains activation records of all active methods. ○ Top of stack denotes the .
○ Remaining parts of stack are (temporarily) suspended.
● When entire body of a method is executed, stack is popped .
⇒ The is returned to the new top
of stack (which was suspended and just became active).
● Execution terminates when the stack becomes empty .
current point of execution
current point of execution
7 of 40
Recursion: Fibonacci (1)
Recall the formal definition of calculating the nth number in a Fibonacci series (denoted as Fn), which is already itself
recursive:
⎧⎪1 ⎪
if n = 1 if n = 2 if n > 2
fib
Fn = ⎨1 ⎪
⎪⎩Fn1 + Fn2
int (int n) {
int result;
if(n == 1) { /* base case */ result = 1; }
else if(n == 2) { /* base case */ result = 1; } else { /* recursive case */
result = fib(n – 1) + fib(n – 2); }
return result; }
8 of 40
Recursion: Fibonacci (2)
fib(5)
= {fib(5)
fib(4) + fib(3)
= fib(4) + fib(3); push(fib(5)); suspended: ⟨fib(5)⟩; active: fib(4)}
= {fib(4)
( fib(3) + fib(2) ) + fib(3)
= fib(3) + fib(2); suspended: ⟨fib(4), fib(5)⟩; active: fib(3)}
= {fib(3) = fib(2) + fib(1); suspended: ⟨fib(3), fib(4), fib(5)⟩; active: fib(2)} (( fib(2) + fib(1) ) + fib(2)) + fib(3)
= {fib(2) returns 1; suspended: ⟨fib(3), fib(4), fib(5)⟩; active: fib(1)} (( 1 + fib(1) ) + fib(2)) + fib(3)
= {fib(1) returns 1; suspended: ⟨fib(3), fib(4), fib(5)⟩; active: fib(3)} (( 1 + 1 ) + fib(2)) + fib(3)
= {fib(3) returns 1 + 1; pop(); suspended: ⟨fib(4), fib(5)⟩; active: fib(2)} (2 + fib(2) ) + fib(3)
= {fib(2) returns 1; suspended: ⟨fib(4), fib(5)⟩; active: fib(4)} (2+1)+fib(3)
= {fib(4) returns 2 + 1; pop(); suspended: ⟨fib(5)⟩; active: fib(3)} 3 + fib(3)
= {fib(3) = fib(2) + fib(1); suspended: ⟨fib(3),fib(5)⟩; active: fib(2)} 3 + ( fib(2) + fib(1))
= {fib(2) returns 3+(1+ fib(1) )
= {fib(1) returns
3+(1+1)
= {fib(3) returns
3+2
= {fib(5) returns
1; suspended: ⟨fib(3), fib(5)⟩; active: fib(1)} 1; suspended: ⟨fib(3), fib(5)⟩; active: fib(3)}
1 + 1; pop() ; suspended: ⟨fib(5)⟩; active: fib(5)} 3 + 2; suspended: ⟨⟩}
9 of 40 5
Java Library: String
public class StringTester {
public static void main(String[] args) {
String s = “abcd”; System.out.println(s.isEmpty()); /* false */
/* Characters in index range [0, 0) */
String t0 = s.substring(0, 0); System.out.println(t0); /* “” */
/* Characters in index range [0, 4) */
String t1 = s.substring(0, 4); System.out.println(t1); /* “abcd” */
/* Characters in index range [1, 3) */
String t2 = s.substring(1, 3); System.out.println(t2); /* “bc” */
String t3 = s.substring(0, 2) + s.substring(2, 4); System.out.println(s.equals(t3)); /* true */ for(int i = 0; i < s.length(); i ++) {
System.out.print(s.charAt(i)); }
System.out.println(); }
}
10 of 40
Recursion: Palindrome (1)
Problem: A palindrome is a word that reads the same forwards and backwards. Write a method that takes a string and determines whether or not it is a palindrome.
System.out.println(isPalindrome("")); true System.out.println(isPalindrome("a")); true System.out.println(isPalindrome("madam")); true System.out.println(isPalindrome("racecar")); true System.out.println(isPalindrome("man")); false
Base Case 1: Empty string → Return true immediately. Base Case 2: String of length 1 → Return true immediately. Recursive Case: String of length ≥ 2 →
○ 1st and last characters match, and
○ the rest (i.e., middle) of the string is a palindrome .
11 of 40
Recursion: Palindrome (2)
boolean (String word) { if(word.length() == 0 || word.length() == 1) {
/* base case */
return true; }
else {
/* recursive case */
char firstChar = word.charAt(0);
char lastChar = word.charAt(word.length() - 1); String middle = word.substring(1, word.length() - 1); return
12 of 40
firstChar == lastChar
/* See the API of java.lang.String.substring. */ && isPalindrome (middle);
} }
isPalindrome
Recursion: Reverse of String (1)
Problem: The reverse of a string is written backwards. Write a
method that takes a string and returns its reverse.
System.out.println(reverseOf("")); /* "" */ System.out.println(reverseOf("a")); "a" System.out.println(reverseOf("ab")); "ba" System.out.println(reverseOf("abc")); "cba" System.out.println(reverseof("abcd")); "dcba"
Base Case 1: Empty string → Return empty string. Base Case 2: String of length 1 → Return that string. Recursive Case: String of length ≥ 2 →
1) Head of string (i.e., first character)
2) Reverse of the tail of string (i.e., all but the first character)
Return the concatenation of 1) and 2). 13 of 40
Recursion: Reverse of a String (2)
String (String s) { if(s.isEmpty()) { /* base case 1 */
return ""; }
else if(s.length() == 1) { /* base case 2 */ return s;
}
else { /* recursive case */
String tail = s.substring(1, s.length()); String reverseOfTail = reverseOf (tail);
char head = s.charAt(0);
return reverseOfTail + head; }
}
reverseOf
14 of 40
Recursion: Number of Occurrences (1) Problem: Write a method that takes a string s and a character
c, then count the number of occurrences of c in s.
System.out.println(occurrencesOf("", ’a’)); /* 0 */ System.out.println(occurrencesOf("a", ’a’)); /* 1 */ System.out.println(occurrencesOf("b", ’a’)); /* 0 */ System.out.println(occurrencesOf("baaba", ’a’)); /* 3 */ System.out.println(occurrencesOf("baaba", ’b’)); /* 2 */ System.out.println(occurrencesOf("baaba", ’c’)); /* 0 */
Base Case: Empty string → Return 0. Recursive Case: String of length ≥ 1 →
1) Head of s (i.e., first character)
2) Number of occurrences of c in the tail of s (i.e., all but the first character)
If head is equal to c, return 1 + 2).
If head is not equal to c, return 0 + 2). 15 of 40
Recursion: Number of Occurrences (2)
int (String s, char c) { if(s.isEmpty()) {
/* Base Case */
return 0; }
else {
/* Recursive Case */
char head = s.charAt(0);
String tail = s.substring(1, s.length()); if(head == c) {
return 1 + occurrencesOf (tail, c); }
else {
return 0 + occurrencesOf (tail, c);
} }
}
occurrencesOf
16 of 40
Recursion: All Positive (1)
Problem: Determine if an array of integers are all positive.
System.out.println(allPositive({})); /* true */ System.out.println(allPositive({1, 2, 3, 4, 5})); /* true */ System.out.println(allPositive({1, 2, -3, 4, 5})); /* false */
Base Case: Empty array → Return true immediately.
The base case is true ∵ we can not find a counter-example
(i.e., a number not positive) from an empty array. Recursive Case: Non-Empty array →
○ 1st element positive, and
○ the rest of the array is all positive .
Exercise: Write a method boolean somePostive(int[] a) which recursively returns true if there is some positive number in a, and false if there are no positive numbers in a. Hint: What to return in the base case of an empty array? [false]
∵ No witness (i.e., a positive number) from an empty array 17 of 40
Making Recursive Calls on an Array
● Recursive calls denote solutions to smaller sub-problems. ● Naively, explicitly create a new, smaller array:
void m(int[] a) {
int[] subArray = new int[a.length - 1];
for(int i = ; i < a.length; i ++) { subArray[0] = a[i - 1]; } m(subArray) }
● For efficiency, we pass the same array by reference and specify the range of indices to be considered:
void m(int[] a, int from, int to) { if(from == to) { /* base case */ } else { m(a, , to) } }
18 of 40
1
from + 1
m(a, 0, a.length - 1) m(a, 1, a.length - 1) m(a, 2, a.length - 1) ...
[ Initial call; entire array ] [1str.c.onarrayofsizea.length−1] [2ndr.c.onarrayofsizea.length−2]
m(a, a.length-1, a.length-1) [ Last r.c. on array of size 1 ]
Recursion: All Positive (2)
boolean allPositive(int[] a) {
return allPositiveHelper (a, 0, a.length - 1);
}
boolean allPositiveHelper (int[] a, int from, int to) { if (from > to) { /* base case 1: empty range */
return true; }
else if(from == to) { /* base case 2: range of one element */ return a[from] > 0;
}
else { /* recursive case */
return a[from] > 0 && allPositiveHelper (a, from + 1, to); }
}
19 of 40
Recursion: Is an Array Sorted? (1)
Problem: Determine if an array of integers are sorted in a
non-descending order.
System.out.println(isSorted({})); true System.out.println(isSorted({1, 2, 2, 3, 4})); true System.out.println(isSorted({1, 2, 2, 1, 3})); false
Base Case: Empty array → Return true immediately.
The base case is true ∵ we can not find a counter-example (i.e., a pair of adjacent numbers that are not sorted in a non-descending order) from an empty array.
Recursive Case: Non-Empty array →
○ 1st and 2nd elements are sorted in a non-descending order, and ○ the rest of the array, starting from the 2nd element,
are sorted in a non-descending positive . 20 of 40
Recursion: Is an Array Sorted? (2)
boolean isSorted(int[] a) {
return isSortedHelper (a, 0, a.length – 1);
}
boolean isSortedHelper (int[] a, int from, int to) { if (from > to) { /* base case 1: empty range */
return true; }
else if(from == to) { /* base case 2: range of one element */ return true;
}
else {
return a[from] <= a[from + 1]
&& isSortedHelper (a, from + 1, to);
} }
21 of 40
Recursion: Sorting an Array (1)
Problem: Sort an array into a non-descending order, using the
selection-sort strategy.
Base Case: Arrays of size 0 or 1 → Completed immediately. Recursive Case: Non-Empty array a →
Run an iteration from indices i = 0 to a.length − 1. In each iteration:
In index range [i , a.length − 1], recursively compute the minimum element .
22 of 40
Swap
and if e < a[i].
e
a[i ]
e
Recursion: Sorting an Array (2)
public static int (int[] a, int from, int to) { if(from == to) { return from; }
else {
int minIndexOfTail = getMinIndex(a, from + 1, to); if(a[from] < a[minIndexOfTail]) { return from; } else { return minIndexOfTail; }
} }
public static void selectionSort(int[] a) {
if(a.length == 0 || a.length == 1) { /* sorted, do nothing */ } else {
for(int i = 0; i < a.length; i ++) {
int minIndex = getMinIndex (a, i, a.length - 1);
/* swap a[i] and a[minIndex] */
int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp;
} }
}
getMinIndex
23 of 40
Recursion: Binary Search (1) ● Searching Problem
Input: A number a and a sorted list of n numbers ⟨a , a ,..., a ⟩suchthata ≤a ≤...≤a
12n12n Output: Whether or not a exists in the input list
● An Efficient Recursive Solution Base Case: Empty list → False. Recursive Case: List of size ≥ 1 →
○ Compare the middle element against a. All elements to the left of middle are ≤ a
All elements to the right of middle are ≥ a
○ If the middle element is equal to a → True. ○ If the middle element is not equal to a:
If a < middle, recursively find a on the left half. If a > middle, recursively find a on the right half.
24 of 40
Recursion: Binary Search (2)
boolean binarySearch(int[] sorted, int key) {
return binarySearchHelper (sorted, 0, sorted.length – 1, key);
}
boolean binarySearchHelper (int[] sorted, int from, int to, int key) {
if (from > to) { /* base case 1: empty range */ return false; }
else if(from == to) { /* base case 2: range of one element */ return sorted[from] == key; }
else {
int middle = (from + to) / 2;
int middleValue = sorted[middle]; if(key < middleValue) {
return binarySearchHelper (sorted, from, middle - 1, key); }
else if (key > middleValue) {
return binarySearchHelper (sorted, middle + 1, to, key);
}
else { return true; }
}
}
25 of 40
Tower of Hanoi: Specification
The Tower of Hanoi
Tower of Hanoi puzzle is attributed to the French mathematician Edouard Lucas, who came up with it in 1883.
● Given: A tower of 8 disks, initially His formulation involved three pegs and eight distinctly-sized
disks stacked on one of the pegs from the biggest on the stacked in decreasing size on
bottom to the smallest on the top, like so:
one of 3 pegs ● Rules:
○ Move only one disk at a time
○ Never move a larger disk onto a
smaller one
● Problem: Transfer the entire tower to one of the other pegs.
26 of 40
Tower of Hanoi: Strategy
● Generalize the problem by considering n disks. ● Introduce appropriate notation:
○ Tn denotes the minimum number of moves required to to transfer n disks from one to another under the rules.
● General patterns are easier to perceive when the extreme or base cases are well understood.
○ Look at small cases first: T1 = 1
T2 = 3
How about T3? Does it help us perceive the general case of n?
27 of 40
Tower of Hanoi: A General Solution Pattern
A possible (yet to be proved as optimal) solution requires 3 steps:
1. Transfer the n – 1 smallest disks to a different peg. 2. Move the largest to the remaining free peg.
3. Transfer the n – 1 disks back onto the largest disk.
How many moves are required from the above 3 steps?
(2×Tn1)+1
However, we have only proved that the # moves required by this
solution are sufficient:
Tn ≤(2×Tn1)+1
But are the above steps all necessary? Can you justify?
Tn ≥(2×Tn1)+1
28 of 40
Tower of Hanoi: Recurrence Relation for Tn
We end up with the following recurrence relation that allows us to
compute Tn for any n we like: T0 = 0
Tn = (2×Tn1)+1 forn>0
However, the above relation only gives us indirect information:
To calculate Tn, first calculate Tn1, which requires the calculation of Tn2, and so on.
Instead, we need a closed-form solution to the above recurrence relation, which allows us to directly calculate the value of Tn.
29 of 40
Tower of Hanoi:
A Hypothesized Closed Form Solution to Tn
T0 =0
T1 = 2×T0+1 = 1
T2 = 2×T1+1 = 3
T3 = 2×T2+1 = 7
T4 = 2×T3+1 = 15
T5 = 2×T4+1 = 31
T6 = 2×T5+1 = 63
…
Guess:
Tn = 2n − 1 for n ≥ 0 Prove by mathematical induction.
30 of 40
Tower of Hanoi:
Prove by Mathematical Induction
Basis: Induction:
Assume that then
T0 = 20 − 1 = 0 Tn1 = 2n1 − 1
31 of 40
Tn
= {Recurrence relation for Tn }
(2×Tn1)+1
= {Inductive assumption}
(2×(2n1 −1))+1 = {Arithmetic}
2n − 1
Revisiting the Tower of Hanoi
Given: A tower of 8 disks, initially stacked in decreasing size on one of 3 pegs.
This shall require moves to complete.
T8 = 28 − 1 = 255
32 of 40
Tower of Hanoi in Java (1)
void towerOfHanoi(String[] disks) {
tohHelper (disks, 0, disks.length – 1, 1, 3);
}
void tohHelper(String[] disks, int from, int to, int p1, int p2) {
if(from > to) { } else if(from == to) {
print(“move ” + disks[to] + ” from ” + p1 + ” to ” + p2); }
else {
int intermediate = 6 – p1 – p2;
tohHelper (disks, from, to – 1, p1, intermediate); print(“move ” + disks[to] + ” from ” + p1 + ” to ” + p2);
tohHelper (disks, from, to – 1, intermediate, p2); }
}
● moves disks
{disks[from], disks[from + 1],. . . , disks[to]} from peg p1 to peg p2.
● Peg id’s are 1, 2, and 3 ⇒ The intermediate one is 6−p1−p2. 33 of 40
tohHelper(disks, from, to, p1, p2)
Tower of Hanoi in Java (2)
Say ds (disks) is {A,B,C}, where A < B < C.
⎧⎪ ⎧⎪ tohH(ds, 0,0,p1,p3) = {
⎪ ⎪
Move A: p1 to p3
Move A: p3 to p2
Move A: p2 to p1
Move A: p1 to p3
⎪ ⎪
⎪ ⎪
⎪ ⎪{A} ⎪ ⎪ ⎪⎪
⎪ tohH(ds, 0,1 ,p1,p2) = ⎨
⎪ {A,B} ⎪
⎪
⎪
⎪
⎪ tohH(ds, 0,2 ,p1,p3) = ⎨
⎪ ⎪ {A,B,C} ⎪ ⎪
⎪
⎪
⎪
⎪ ⎩{A}
⎪ ⎪ ⎪⎪
Move B: p1 to p2 tohH(ds, 0,0,p3,p2) = {
Move C: p1 to p3
34 of 40
⎪ ⎪⎪
⎪ ⎪
⎪ ⎪{A} ⎪ ⎪ ⎪⎪
⎪ tohH(ds, 0,1 ,p2,p3) = ⎨
⎪ ⎩
⎪ {A,B} ⎪
⎪
⎪ ⎪ ⎪
⎧
⎪ tohH(ds, 0,0,p2,p1) = {
⎪ ⎪ ⎪⎪
Move B: p2 to p3 tohH(ds, 0,0,p1,p3) = {
⎩{A}
⎪
Tower of Hanoi in Java (3)
tohHelper({A, B, C}, 0, 1, p1, p2)
tohHelper({A, B, C}, 0, 0, p1, p3) move B from p1 to p2
move A from p1 to p3
towerOfHanio({A, B, C})
tohHelper({A, B, C}, 0, 2, p1, p3)
move C from p1 to p3
tohHelper({A, B, C}, 0, 0, p3, p2) tohHelper({A, B, C}, 0, 0, p2, p1)
move A from p3 to p2 move A from p2 to p1
tohHelper({A, B, C}, 0, 1, p2, p3)
move B from p2 to p3
tohHelper({A, B, C}, 0, 0, p1, p3)
move A from p1 to p3
35 of 40
Recursive Methods: Correctness Proofs
1} 2
3
4
5
boolean allPositive(int[] a) { return (a, 0, a.length - 1); boolean allPosH (int[] a, int from, int to) {
if (from > to) { return true; }
else if(from == to) { return a[from] > 0; }
else { return a[from] > 0 && (a, from + 1, to); } }
allPosH
allPosH
● Via mathematical induction, prove that allPosH is correct: Base Cases
●
is correct by invoking
, examining the entire array.
36 of 40
In an empty array, there is no non-positive number ∴ result is true. [L3]
In an array of size 1, the only one elements determines the result. [L4] Inductive Cases
Inductive Hypothesis: returns true if a[from + 1], a[from + 2], . . . , a[to] are all positive; false otherwise. allPosH(a, from, to) should return true if: 1) a[from] is positive;
2) a[from + 1], a[from + 2], . . . , a[to] are all positive.
By , result is a[from] > 0 ∧ . [L5]
allPosH(a, from + 1, to)
and
allPositive(a)
I.H.
[L1]
allPosH(a, 0, a.length – 1)
allPosH(a, from + 1, to)
Beyond this lecture . . .
● Notes on Recursion: http://www.eecs.yorku.ca/ ̃jackie/teaching/
lectures/2017/F/EECS2030/slides/EECS2030_F17_
Notes_Recursion.pdf ● API for String:
https://docs.oracle.com/javase/8/docs/api/
java/lang/String.html
● Fantastic resources for sharpening your recursive skills for the exam:
http://codingbat.com/java/Recursion-1
http://codingbat.com/java/Recursion-2
● The best approach to learning about recursion is via a
functional programming language:
Haskell Tutorial: https://www.haskell.org/tutorial/ 37 of 40
Index (1)
Recursion: Principle
Recursion: Factorial (1) Recursion: Factorial (2) Recursion: Factorial (3) Recursion: Factorial (4)
Tracing Recursion using a Stack Recursion: Fibonacci (1) Recursion: Fibonacci (2)
Java Library: String
Recursion: Palindrome (1) Recursion: Palindrome (2) Recursion: Reverse of a String (1) Recursion: Reverse of a String (2)
Recursion: Number of Occurrences (1)
38 of 40
Index (2)
Recursion: Number of Occurrences (2) Recursion: All Positive (1)
Making Recursive Calls on an Array Recursion: All Positive (2)
Recursion: Is an Array Sorted? (1) Recursion: Is an Array Sorted? (2) Recursion: Sorting an Array (1) Recursion: Sorting an Array (2) Recursion: Binary Search (1) Recursion: Binary Search (2) Tower of Hanoi: Specification Tower of Hanoi: Strategy
Tower of Hanoi: A General Solution Pattern
Tower of Hanoi: Recurrence Relation for Tn 39 of 40
Index (3)
Tower of Hanoi:
A Hypothesized Closed Form Solution to Tn
Tower of Hanoi:
Prove by Mathematical Induction
Revisiting the Tower of Hanoi
Tower of Hanoi in Java (1)
Tower of Hanoi in Java (2)
Tower of Hanoi in Java (3)
Recursive Methods: Correctness Proofs
Beyond this lecture . . . 40 of 40