1Appendix C
Recurrences
Recurrences
and
Recursive algorithms
2Appendix C
Recurrences
Recursive algorithms
A recursive problem is one that can be defined in terms of smaller instances of
the same problem. Searching in a sorted array with Binary Search is such an
example.
Noticing that a problem has a recursive structure can help you write an
algorithm for solving it.
Some benefits to recursive algorithms are that they are easy to write down
and easy to prove correct – just use induction.
3Appendix C
Recurrences
Recursive algorithms: Correctness
Induction and recursion go hand in hand.
Induction: a proof strategy where we show
• a base case
• how to prove a statement about n,
assuming it is true of n-1
Recursion: a way of defining a problem where we must state
• a base case
• how to solve a problem of size n,
assuming we can solve a problem of some smaller size
4Appendix C
Recurrences
When weak and when strong induction?
Weak induction:
If a recursive algorithm solves a problem of size n by turning it into a smaller
problem of size n-1, we use regular (weak) induction.
• Base case: k=0 (or k=1) is true.
• Inductive step: If the inductive hypothesis is true for k=n-1,
then it is also true for k=n.
Strong induction:
If a recursive algorithm solves a problem of size n by turning it into a problem
of some other smaller size than just n-1, we must use strong induction.
• Base cases: Cases k=1,…,n-1 are true.
• Inductive step: If the inductive hypothesis is true for k=1,…,n-1
(this is a stronger assumption than above!),
then it is also true for k=n.
Because we can (not have to, though!) use all n-1 statements (k=1,…,n-1 is
true) to prove k=n is true, strong induction is a more flexible proof
technique than weak induction.
5Appendix C
Recurrences
Solving recurrences (0finding a closed form)
Guess-and-check
Start with small values of n and look for a pattern. Confirm your guess with a
proof by induction.
Unravel
Start with the general recurrence and keep replacing n with smaller input
values. Keep unraveling until you reach the base case.
[[Characteristic polynomial]]
If the recursion is of a certain form, you can guess that the closed form is Cwn
and solve for w by finding the root of a polynomial.
6Appendix C
Recurrences
Recurrence 1
Maximum number of edges
7Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
n=1
n=2
n=3
n=4
8Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
n=1
n=2
n=3
n=4
9Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
Guess and Check, then proof by induction.
10Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
Guess and Check, then proof by induction.
11Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
Unravel the recurrence.
12Appendix C
Recurrences
Undirected graphs
What is the maximum number of edges in a simple undirected graph with n
vertices?
Unravel the recurrence.
13Appendix C
Recurrences
Recurrence 2
f(n) = 3 f(n-1)+2
14Appendix C
Recurrences
Exercise
Solve the following recurrence (“Guess and check”):
15Appendix C
Recurrences
Exercise
Solve the following recurrence (“Unravel”):
16Appendix C
Recurrences
Recurrence 3
Towers of Hanoi
17Appendix C
Recurrences
Example: Towers of Hanoi
“In the temple of Brahma in Hanoi there is a brass platform with three
diamond needles and 64 golden discs all of different sizes. At the
beginning of time the discs were placed on the first needle in a pile
from largest up to smallest. The priests of the temple are transferring
the discs to another needle one at a time so that no disc ever rests on a
smaller disc. When they finish, time and the world will end.”
18Appendix C
Recurrences
1 disc: 1 move
http://www.texample.net/tikz/examples/towers-of-hanoi/
19Appendix C
Recurrences
2 discs: 1+1+1=3 moves
http://www.texample.net/tikz/examples/towers-of-hanoi/
20Appendix C
Recurrences
3 discs: 3+1+3=7 moves
http://www.texample.net/tikz/examples/towers-of-hanoi/
21Appendix C
Recurrences
4 discs: 7+1+7=15 moves
http://www.texample.net/tikz/examples/towers-of-hanoi/
22Appendix C
Recurrences
Example: Towers of Hanoi
The solution has three steps: If T(n) is the number of moves
required to solve the puzzle with
n disks, we have:
1. Move the stack of the smallest T(n-1) moves
n-1 disks to an empty pole.
2. Move the largest disk to an 1 move
empty pole.
3. Move the stack of the smallest T(n-1) moves
n-1 disks to the pole with the
largest disk.
Therefore, T(n) = 2T(n-1) + 1.
23Appendix C
Recurrences
Example: Towers of Hanoi (Time Analysis 1)
T(n) = 2T(n-1) + 1
„Guess and Check …“
Try plugging in small values of n and guessing a pattern.
Confirm your guess with a proof by induction.
???
24Appendix C
Recurrences
Example: Towers of Hanoi (Time Analysis 1)
T(n) = 2T(n-1) + 1 Proof by induction on n
„Guess and Check, then proof by induction“
Try plugging in small values of n and guessing a pattern.
Confirm your guess with a proof by induction.
Base case: n=1, T(1)=1. Correct.
Inductive Hypothesis: T(n-1) = 2n-1- 1
Inductive Step:
T(n) = 2 T(n-1) + 1
T(n) = 2 (2n-1- 1) + 1
= 2n – 1
25Appendix C
Recurrences
Example: Towers of Hanoi (Time Analysis 2)
„Unraveling the recurrence“
Start with the general recurrence, and keep replacing
to get the formula in terms of smaller input values.
Keep unraveling until you reach the base case.
2^64 seconds
1,84467E+19 seconds
3,07446E+17 minutes
5,1241E+15 hours
2,13504E+14 days
5,84942E+11 years
5849424174 centuries
> 5 billion centuries
26Appendix C
Recurrences
Recurrence 4
Binary Strings
27Appendix C
Recurrences
Example: Binary strings avoiding 00
How many binary strings of length n are there with no two consecutive 0’s?
Any such binary string looks like 1_______ OR 01_______
What goes in the blanks? A binary string of shorter length that also avoids 00.
Let B(n) be the number of such length n strings.
To start off this recurrence, we must know two base cases:
B(0)=1 (the empty binary string)
B(1)=2 (the string 1 and the string 0)
28Appendix C
Recurrences
Example: Binary strings avoiding 00
Recurrence: B(0)=1
B(1)=2
B(n)=B(n-1)+B(n-2)
Fibonacci Numbers
(Bernoulli, Euler)
n B(n)
0 1
1 2
2 3
3 5
4 8
5 13
6 21
7 34
29Appendix C
Recurrences
Recurrence 5
Ternary Strings 1
30Appendix C
Recurrences
Ternary Strings
A ternary string is like a binary string except it uses three symbols, 0, 1, and 2.
For example,
12210021
is a ternary string of length 8.
Let T(n) be the number of ternary strings of
length n with the property that there is never
a 2 appearing anywhere after a 0.
For example,
12120110
has this property, but
10120012
does not. Write a recurrence for T(n).
31Appendix C
Recurrences
Ternary Strings
A ternary string is like a binary string except it uses three symbols, 0, 1, and 2.
For example,
12210021
is a ternary string of length 8.
Let T(n) be the number of ternary strings of
length n with the property that there is never
a 2 appearing anywhere after a 0.
For example,
12120110
has this property, but
10120012
does not. Write a recurrence for T(n).
n T(n) Strings
0 1 epsilon
1 3 0 1 2
2 8
00 01 02
10 11 12
20 21 22
3 20
000 001 002
010 011 012
100 101 102
110 111 112
200 201 202
210 211 212
120 121 122
220 221 222
2 x T(n-1) + 2^(n-1)
32Appendix C
Recurrences
Ternary Strings
33Appendix C
Recurrences
Recurrence 6
Ternary Strings 2
34Appendix C
Recurrences
Ternary Strings (Midterm: Extra Question 2018)
Let T(n) be the number of ternary strings of length n with the property that
there is never a 0 appearing anywhere after a 1 or a 2.
Write a recurrence for T(n).
35Appendix C
Recurrences
Ternary Strings (Midterm: Extra Question 2018)
Let T(n) be the number of ternary strings of length n with the property that
there is never a 0 appearing anywhere after a 1 or a 2.
Write a recurrence for T(n).
n T(n) strings
0 1 epsilon
1 3 0 1 2
2 7
01 02 00
11 12 10
21 22 20
3 15
011 012 010
111 112 110
211 212 210
021 022 020
121 122 120
221 222 220
001 002 000
2 T(n-1) + 1
n T(n) strings
0 1 epsilon
1 3 0 1 2
2 7
01 02 00
11 12 10
21 22 20
3 15
011 012 010
111 112 110
211 212 210
021 022 020
121 122 120
221 222 220
001 002 000
T(n-1) + 2n
2T(n-1)+1 = T(n-1)+2^n
T(n-1)=2^n-1
T(n)=2^(n+1)-1
By constructing this
bijection, we can solve
the recurrence!
Foliennummer 1
Recursive algorithms
Recursive algorithms: Correctness
When weak and when strong induction?
Solving recurrences (0finding a closed form)
Foliennummer 6
Undirected graphs
Undirected graphs
Undirected graphs
Undirected graphs
Undirected graphs
Undirected graphs
Foliennummer 13
Exercise
Exercise
Foliennummer 16
Example: Towers of Hanoi
1 disc: 1 move
2 discs: 1+1+1=3 moves
3 discs: 3+1+3=7 moves
4 discs: 7+1+7=15 moves
Example: Towers of Hanoi
Example: Towers of Hanoi (Time Analysis 1)
Example: Towers of Hanoi (Time Analysis 1)
Example: Towers of Hanoi (Time Analysis 2)
Foliennummer 26
Example: Binary strings avoiding 00
Example: Binary strings avoiding 00
Foliennummer 29
Ternary Strings
Ternary Strings
Ternary Strings
Foliennummer 33
Ternary Strings (Midterm: Extra Question 2018)
Ternary Strings (Midterm: Extra Question 2018)
Foliennummer 36
Example: Exponentiation (Correctness Proof)
Example: Exponentiation (Correctness Proof)
Example: Exponentiation (Time analysis)
Example: Exponentiation (Time analysis)
Example: Exponentiation (Time analysis)
Example: Exponentiation (Time analysis)
Example: Exponentiation (Time analysis)
Foliennummer 44
Merging sorted arrays
Iterative Merge: Correctness
Recursive Merge
Recursive Merge
Recursive Merge
Recursive Merge: Time analysis
Recursive Merge: Time analysis
Recursive Merge: Time analysis