Recursion
EECS2030 B: Advanced Object Oriented Programming Fall 2018
CHEN-WEI WANG
Beyond this lecture . . .
● 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/
2 of 50
Recursion: Principle
● is useful in expressing solutions to problems that can be defined:
○ Base Cases: Small problem instances immediately solvable. ○ Recursive Cases:
● Largeprobleminstancesnotimmediatelysolvable.
● Solvebyreusingsolution(s)tostrictlysmallerprobleminstances.
● Similar idea learnt in high school: [ mathematical induction ] ● Recursion can be easily expressed programmatically in Java:
Recursion
recursively
m
(i) {
if(i == …) { /* base case: do something directly */ } else {
m (j);/* recursive call with strictly smaller value */ }
}
○ 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. 3 of 50
Tracing Method Calls via 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
4 of 50
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)!.
5 of 50
Common Errors of Recursive Methods
● Missing Base Case(s).
int (int n) {
return n * (n - 1);
}
factorial
factorial
Base case(s) are meant as points of stopping growing the
runtime stack.
● Recursive Calls on Non-Smaller Problem Instances.
int (int n) {
if(n == 0) { /* base case */ return 1; }
else { /* recursive case */ return n * factorial (n); }
}
factorial
Recursive calls on strictly smaller problem instances are
meant for moving gradually towards the base case(s).
● In both cases, a StackOverflowException will be thrown. 6 of 50
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
7 of 50
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.
8 of 50
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 ]
9 of 50
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; }
10 of 50
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: ⟨⟩}
11 of 505
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(); }
}
12 of 50
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 .
13 of 50
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
14 of 50
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). 15 of 50
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
16 of 50
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). 17 of 50
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
18 of 50
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) {
if(a.length == 0) { /* base case */ }
else if(a.length == 1) { /* base case */ } else {
int[] sub = new int[a.length - 1];
for(int i = ; i < a.length; i ++) { sub[0] = a[i - 1]; } m(sub) } }
1
● For efficiency, we pass the reference of the same array and specify the range of indices to be considered:
void m(int[] a, int from, int to) { if(from > to) { /* base case */ }
else if(from == to) { /* base case */ } else { m(a, , to) } }
from + 1
● m(a, 0, a.length – 1) [ Initial call; entire array ]
● m(a, 1, a.length – 1) [1str.c.onarrayofsizea.length−1] 19 of 50 ● m(a, a.length-1, a.length-1) [ Last r.c. on array of size 1 ]
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 20 of 50
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); }
}
21 of 50
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 . 22 of 50
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);
} }
23 of 50
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.
24 of 50
● Inanemptyarray,thereisnonon-positivenumber∴resultistrue.[L3]
● In an array of size 1, the only one elements determines the result. [L4] Inductive Cases
●
●
●
InductiveHypothesis: returnstrueif 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 ,resultisa[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)
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. ● Allelementstotheleftofmiddleare≤a
● Allelementstotherightofmiddleare≥a
○ If the middle element is equal to a → True. ○ If the middle element is not equal to a:
● Ifa
25 of 50
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; }
}
}
26 of 50
Running Time: Binary Search (1)
We use T(n) to denote the running time function of a binary search, where n is the size of the input array.
⎧⎪ ⎪ ⎪ T ( 0 ) = 1 ⎨T(1) = 1
⎪ T(n) = T(n)+1 where n≥2 ⎩2
To solve this recurrence relation, we study the pattern of T(n) and observe how it reaches the base case(s).
27 of 50
Running Time: Binary Search (2)
Without loss of generality, assume n = 2i for some non-negative i. T(n) = T(n)+1
2n
= (T(4)+1)+ 1
1 time T(n)
n
= ((T(8)+1)+ 1)+1
2
T(n) = …
= ((( 1
)+1)…)+1
2 times 4
T( n )=T(1) 2log n
log n times
∴ T(n) is O(log n) 28 of 50
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.
29 of 50
Tower of Hanoi: A Recursive Solution
The general, recursive 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.
30 of 50
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 ori, int des){
if(from > to) { } else if(from == to) {
print(“move ” + disks[to] + ” from ” + ori + ” to ” + des); }
else {
int intermediate = 6 – ori – des;
tohHelper (disks, from, to – 1, ori, intermediate); print(“move ” + disks[to] + ” from ” + ori + ” to ” + des);
tohHelper (disks, from, to – 1, intermediate, des); }
}
● moves disks {disks[from], disks[from + 1],. . . , disks[to]} from peg ori to peg des.
● Peg id’s are 1, 2, and 3 ⇒ The intermediate one is 6−ori −des. 31 of 50
tohHelper(disks, from, to, ori, des)
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
32 of 50
⎪ ⎪⎪
⎪ ⎪
⎪ ⎪{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
33 of 50
Running Time: Tower of Hanoi (1)
● Generalize the problem by considering n disks.
● Let T (n) denote the number of moves required to to transfer n
disks from one to another under the rules.
● Recall the general solution pattern:
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.
● We end up with the following recurrence relation that allows us to compute Tn for any n we like:
T(1) = 1
{ T(n) = 2×T(n−1)+1 wheren>0
● To solve this recurrence relation, we study the pattern of T(n)
and observe how it reaches the base case(s).
34 of 50
Running Time: Tower of Hanoi (2)
T(n) = 2×T(n−1)+1
= 2×(2×T(n−2)+1)+1
T (n−1)
= 2×(2×(2×T(n−3)+1)+1)+1
= …
T (n−2)
T (2)
= 2×(2×(2×(⋅⋅⋅×(2×T(1)+1)+…)+1)+1)+1
= 2n−1+(n−1)
∴ T(n) is O(2n) 35 of 50
T (n−3)
Recursion: Merge Sort
● Sorting Problem
Input: A list of n numbers ⟨a1, a2, …, an⟩
Output: A permutation (reordering) ⟨a′ , a′ , . . . , a′ ⟩ of the
input list such that a′ ≤ a′ ≤…≤ a′ 12n
● Recursive Solution
Base Case 1: Empty list → Automatically sorted.
Base Case 2: List of size 1 → Automatically sorted. Recursive Case: List of size ≥ 2 →
○ Split the list into two (unsorted) halves: L and R; ○ Recursively sort L and R: sortedL and sortedR; ○ Return the merge of sortedL and sortedR.
12n
36 of 50
Recursion: Merge Sort in Java (1)
/* Assumption: L and R are both already sorted. */
private List
int i = 0;
int j = 0;
while(i < L.size() && j < R.size()) {
if( L.get(i) <= R.get(j) ) { merge.add(L.get(i)); i ++; }
else { merge.add(R.get(j)); j ++; } }
/* If i >= L.size(), then this for loop is skipped. */
for(int k = i; k < L.size(); k ++) { merge.add(L.get(k)); } /* If j >= R.size(), then this for loop is skipped. */ for(int k = j; k < R.size(); k ++) { merge.add(R.get(k)); }
}
return merge; }
RT(merge)? [ O(n) ]
37 of 50
Recursion: Merge Sort in Java (2)
public List
if(list.size() == 0) { sortedList = new ArrayList<>(); } else if(list.size() == 1) {
sortedList = new ArrayList<>();
sortedList.add(list.get(0)); }
else {
int middle = list.size() / 2;
List
List
sortedList = (sortedLeft, sortedRight);
}
return sortedList; }
merge
sort
sort
sort
RT(sort)=RT(merge)×# splits until size 0 or 1
38 of 50 O(n) O(log n)
Recursion: Merge Sort Example (1)
(1) Start with input list of size 8 (2) Split and recur on L of size 4
85 24 63 45 17 31 96 50
17 31 96 50
85 24 63 45
(3) Split and recur on L of size 2 (4) Split and recur on L of size 1, return
17 31 96 50
17 31 96 50
63 45
63 45
85 24
24
39 of 50
85
Recursion: Merge Sort Example (2)
(5) Recur on R of size 1 and return 17 31 96 50
(6) Merge sorted L and R of sizes 1
17 31 96 50
63 45
63 45
85
24 85
24
(7) Return merged list of size 2 (8) Recur on R of size 2
17 31 96 50
17 31 96 50
24 85 63 45
24 85
63 45
40 of 50
Recursion: Merge Sort Example (3)
(9) Split and recur on L of size 1, return 17 31 96 50
24 85
45
(11) Merge sorted L and R of sizes 1, return 17 31 96 50
(10) Recur on R of size 1, return 17 31 96 50
24 85
63
(12) Merge sorted L and R of sizes 2
63
45
17 31 96 50
24 85
24 45 63 85
45 63
41 of 50
Recursion: Merge Sort Example (4)
(13) Recur on R of size 4
24 45 63 85
17 31 96 50
(14) Return a sorted list of size 4 24 45 63 85
17 31 50 96
(15) Merge sorted L and R of sizes 4 (16) Return a sorted list of size 8
24 45 63 85 17 31 50 96
17 24 31 45 50 63 85 96
42 of 50
Recursion: Merge Sort Example (5)
(1) Recursion trees of unsorted lists 85 24 63 45 17 31 96 50
(2) Recursion trees of sorted lists 17 24 31 45 50 63 85 96
85 24 63 45
85 24 63 45
85 24 63 45
17 31 96 50
17 31 96 50
17 31 96 50
24 45 63 85
24 85 45 63
85 24 63 45
17 31 50 96
17 31 50 96
17 31 96 50
43 of 50
Recursion: Merge Sort Running Time (1)
Base Case 1: Empty list → Automatically sorted. Base Case 2: List of size 1 → Automatically sorted. Recursive Case: List of size ≥ 2 →
[ O(1) ] [ O(1) ]
[ O(1) ] HowmanytimestosplituntilLandRhavesize0or1? [O(logn)]
○ Split the list into two (unsorted) halves: L and R; ○ Recursively sort L and R: sortedL and sortedR;
○ Return the merge of sortedL and sortedR. [ O(n) ]
RT
= (RT each RC) × (# RCs)
= (RT merging sortedL and sortedR) × (# splits until bases) = n⋅logn
44 of 50
Recursion: Merge Sort Running Time (2)
Height
Time per level
O(n)
O(n)
O(n)
n
n/2
n/2
O(log n)
n/4
n/4
n/4
n/4
45 of 50
Total time: O(nlogn)
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/ 46 of 50
Index (1)
Beyond this lecture . . .
Recursion: Principle
Tracing Method Calls via a Stack Recursion: Factorial (1)
Common Errors of Recursive Methods Recursion: Factorial (2)
Recursion: Factorial (3)
Recursion: Factorial (4)
Recursion: Fibonacci (1)
Recursion: Fibonacci (2)
Java Library: String
Recursion: Palindrome (1)
Recursion: Palindrome (2)
Recursion: Reverse of a String (1)
47 of 50
Index (2)
Recursion: Reverse of a String (2) Recursion: Number of Occurrences (1) Recursion: Number of Occurrences (2) Making Recursive Calls on an Array Recursion: All Positive (1)
Recursion: All Positive (2)
Recursion: Is an Array Sorted? (1) Recursion: Is an Array Sorted? (2) Recursive Methods: Correctness Proofs Recursion: Binary Search (1) Recursion: Binary Search (2)
Running Time: Binary Search (1) Running Time: Binary Search (2)
Tower of Hanoi: Specification
48 of 50
Index (3)
Tower of Hanoi: A Recursive Solution Tower of Hanoi in Java (1)
Tower of Hanoi in Java (2)
Tower of Hanoi in Java (3)
Running Time: Tower of Hanoi (1) Running Time: Tower of Hanoi (2) Recursion: Merge Sort Recursion: Merge Sort Recursion: Merge Sort Recursion: Merge Sort Recursion: Merge Sort Recursion: Merge Sort Recursion: Merge Sort
Recursion: Merge Sort
49 of 50
in Java (1) in Java (2) Example (1) Example (2) Example (3) Example (4) Example (5)
Index (4)
Recursion: Merge Sort Running Time (1)
Recursion: Merge Sort Running Time (2)
Beyond this lecture . . .
50 of 50