COMP9020
Foundations of Computer Science
Lecture 9: Recursion
Administrivia
Week 10 public holiday (Easter Monday)
No lecture April 21
Course review lecture April 28 (14:00-16:00) O’Shane 104
Formatif
W6.P1 task
W7 tasks released today (due Friday) – for discussion in
tutorials
Graph Theory content recording
1
Topic 2: Recursion
Recursion
[LLM] [RW] [Rosen]
Week 6 Recursion Ch. 6, 21 Ch. 4, 7 Ch. 5
Week 7 Induction; Ch. 5, 6.5 Ch. 4, 7 Ch. 5
Algorithmic Analysis Ch. 7 Ch. 3.3
2
Recursion in Computer Science
Fundamental concept in Computer Science
Defining complex objects from simpler ones
Unbounded complexity with a finite description
Recursive Data Structures:
Finite definitions of arbitrarily large objects
Natural numbers
Words
Linked lists
Formulas
Binary trees
3
Recursion in Computer Science
Recursive Algorithms:
Solving problems/calculations by reducing to smaller cases
Factorial
Euclidean gcd algorithm
Towers of Hanoi
Mergesort, Quicksort
Analysis of Recursion:
Reasoning about recursive objects
Induction, Structural Induction
Recursive sequences (e.g. Fibonacci sequence)
Asymptotic analysis of recursive functions
4
Motivating Questions
Task 1
Your boss has asked you to write a program to add up the first n
natural numbers.
Which code is best?
Task 2
The Fibonacci sequence is defined as starting with 0 and 1, and
then the next number in the sequence is the sum of the previous
two:
0, 1, 1, 2, 3, 5, 8, . . .
Your boss has asked you to write a program to compute the n-th
Fibonacci number.
Which code is best?
5
Outline
Recursion
Recursive Data Structures
Recursive Programming
Solving Recurrences
6
Outline
Recursion
Recursive Data Structures
Recursive Programming
Solving Recurrences
7
Recursion
Consists of a basis (B) and recursive process (R).
A sequence/object/algorithm is recursively defined when (typically)
(B) some initial terms are specified, perhaps only the first one;
(R) later terms stated as functional expressions of the earlier
terms.
NB
(R) also called recurrence formula (especially when dealing
with sequences)
8
Example: Factorial
Example
Factorial:
(B) 0! = 1
(R) (n + 1)! = (n + 1) · n!
fact(n):
(B) if(n = 0): 1
(R) else: n ∗ fact(n − 1)
9
Example: Euclid’s gcd algorithm
Example
m
if m = n
gcd(m, n) = gcd(m − n, n) if m > n
gcd(m, n − m) if m < n
10
Example: Towers of Hanoi
There are 3 towers (pegs)
n disks of decreasing size placed on the first tower
You need to move all disks from the first tower to the last
tower
Larger disks cannot be placed on top of smaller disks
The third tower can be used to temporarily hold disks
11
Example: Towers of Hanoi
Questions
Describe a general solution for n disks
How many moves does it take?
12
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
13
Example: Towers of Hanoi
Questions
Describe a general solution for n disks
How many moves does it take? M(n) ≤ 2M(n − 1) + 1
14
Outline
Recursion
Recursive Data Structures
Recursive Programming
Solving Recurrences
15
Example: Natural numbers
Example
A natural number is either 0 (B) or one more than a natural
number (R).
Formal definition of N:
(B) 0 ∈ N
(R) If n ∈ N then (n + 1) ∈ N
16
Example: Odd/Even numbers
Example
The set of even numbers can be defined as:
(B) 0 is an even number
(R) If n is an even number then n + 2 is an even number
17
Example: Odd/Even numbers
Example
The set of odd numbers can be defined as:
(B) 1 is an odd number
(R) If n is an odd number then n + 2 is an odd number
17
Example: Fibonacci numbers
Example
The Fibonacci sequence starts 0, 1, 1, 2, 3, . . . where, after 0, 1,
each term is the sum of the previous two terms.
Formally, the sequence of Fibonacci numbers: F0 , F1 , F2 , . . . where
the n-th Fibonacci number Fn is defined as:
(B) F0 = 0,
(B) F1 = 1,
(R) Fn = Fn−1 + Fn−2
NB
Could also define the Fibonacci sequence as a function
fib : N → F.
18
Example: Linked lists
Example
A linked list is zero or more linked list nodes:
··· ⊥
head
In C:
struct node{
int data;
struct node *next;
}
19
Example: Linked lists
Example
We can view the linked list structure abstractly. A linked list is
either:
(B) an empty list, or
(R) an ordered pair (Data, List).
20
Example: Words over Σ
Example
A word over an alphabet Σ is either λ (B) or a symbol from Σ
followed by a word (R).
Formal definition of Σ∗ :
(B) λ ∈ Σ∗
(R) If w ∈ Σ∗ then aw ∈ Σ∗ for all a ∈ Σ
NB
This matches the recursive definition of a Linked List data type.
21
Example: Expressions in the Proof Assistant
Example
(B) A, B, . . . , Z , a, b, . . . z are expressions
(B) ∅ and U are expressions
(R) If E is an expression then so is (E ) and E c
(R) If E1 and E2 are expressions then:
(E1 ∪ E2 ),
(E1 ∩ E2 ),
(E1 \ E2 ), and
(E1 ⊕ E2 ) are expressions.
22
Example: Propositional formulas
Example
A well-formed formula (wff) over a set of propositional variables,
Prop is defined as:
(B) ⊤ is a wff
(B) ⊥ is a wff
(B) p is a wff for all p ∈ Prop
(R) If φ is a wff then ¬φ is a wff
(R) If φ and ψ are wffs then:
(φ ∧ ψ),
(φ ∨ ψ),
(φ → ψ), and
(φ ↔ ψ) are wffs.
23
Outline
Recursion
Recursive Data Structures
Recursive Programming
Solving Recurrences
24
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
The factorial function:
fact(n):
(B) if(n = 0): 1
(R) else: n ∗ fact(n − 1)
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
Summing the first n natural numbers:
sum(n):
(B) if(n = 0): 0
(R) else: n + sum(n − 1)
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
Summing elements of a linked list:
sum(L):
(B) if(L.isEmpty()):
return 0
(R) else:
return L.data + sum(L.next)
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
Sorting elements of a linked list (insertion sort):
sort(L):
(B) if(L.isEmpty()):
return L
else:
(R) L2 = sort(L.next)
insert L.data into L2
return L2
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
Concatenation of words (defining wv ):
For all w , v ∈ Σ∗ and a ∈ Σ :
(B) λv = v
(R) (aw )v = a(wv )
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
Length of words:
(B) length(λ) = 0
(R) length(aw ) = 1 + length(w )
25
Programming over recursive datatypes
Recursive datatypes make recursive programming/functions easy.
Example
“Evaluation” of a propositional formula
25
Exercise
Exercise
Let Σ be a finite set.
Define append : Σ∗ × Σ → Σ∗ by
append(w , a) = wa
Give a (direct) definition of append [i.e. only concatenates symbols
on the left].
26
Mutual Recursion
Sometimes recursive definitions use more than one function, with
each calling each other.
Example (Fibonacci, again)
Recall:
(B) f (0) = 0; f (1) = 1,
(R) f (n) = f (n − 1) + f (n − 2)
Alternative, mutually recursive definition:
(B) f (1) = 1; g (1) = 0
(R) f (n) = f (n − 1) + g (n − 1)
(R) g (n) = f (n − 1)
f (n) 1 1 f (n − 1)
=
g (n) 1 0 g (n − 1)
27
Outline
Recursion
Recursive Data Structures
Recursive Programming
Solving Recurrences
28
Solving recurrences
Question
How can we (asymptotically) compare recursively defined
functions?
Some practical approaches:
Unwinding the recurrence
Approximating with big-O
The Master Theorem
NB
Each approach gives an informal “solution”: ideally one should
prove a solution is correct (using e.g. induction).
29
Examples
Example (Unwinding)
f (0) = 1 f (n) = 2f (n − 1)
Unwinding:
f (n) = 2f (n − 1)
= 2(2f (n − 2)) = 4f (n − 2)
= 4(2f (n − 3)) = 8f (n − 3)
.. ..
. .
= 2i f (n − i)
.. ..
. .
= 2n f (0) = 2n
30
Examples
Example (Unwinding)
j n k
f (1) = 0 f (n) = 1 + f
2
Unwinding:
f (n) = 1 + f (n/2)
= 1 + (1 + f (n/4)) = 2 + f (n/4)
= 2 + (1 + f (n/8))
.. ..
. .
= i + f (n/2i )
.. ..
. .
= log(n) + f (0) = log(n)
31
Examples
Example (Approximating with big-O)
f (0) = 1 f (1) = 1 f (n) = f (n − 1) + f (n − 2)
Assuming f (n) is increasing:
f (n − 2) ≤ f (n − 1)
so:
f (n) ≤ 2f (n − 1)
so (by unwinding):
f (n) ≤ 2n
so:
f (n) ∈ O(2n )
32
Master Theorem
The following result covers many recurrences that arise in practice
(e.g. divide-and-conquer algorithms)
Theorem
Suppose n
T (n) = a · T + f (n)
b
where f (n) ∈ Θ(nc (log n)k ).
Let d = logb (a). Then:
Case 1: If c < d then T (n) = Θ(nd )
Case 2: If c = d then T (n) = Θ(nc (log n)k+1 )
Case 3: If c > d then T (n) = Θ(f (n))
33
Master Theorem: Examples
Example (Master Theorem)
n
T (n) = T + n2 , T (1) = 1
2
Here a = 1, b = 2, c = 2, k = 0 and d = 0. So we have Case 3
and the solution is
T (n) = Θ(nc ) = Θ(n2 )
34
Master Theorem: Examples
Example (Master Theorem)
Mergesort has n
T (n) = 2T + (n − 1)
2
for the number of comparisons.
Here a = b = 2, c = 1, k = 0 and d = 1. So we have Case 2, and
the solution is
T (n) = Θ(nc log(n)) = O(n log(n))
34
Master Theorem: Examples
Example (Master Theorem)
Unwinding example:
n
T (1) = 0 T (n) = 1 + T (⌊ ⌋)
2
Here a = 1, b = 2, c = 0, k = 0, and d = 0. So we have Case 2,
and the solution is
T (n) = Θ(log(n))
34
The Master Theorem: Pitfalls
NB
a, b, c, k have to be constants (not dependent on n).
Only one recursive term.
Recursive term is of the form T (n/b), not T (n − b).
Solution is only an asymptotic bound.
Examples
The Master theorem does not apply to any of these:
T (n) = 2n T (n/2) + n2
T (n) = T (n/5) + T (7n/10) + n
T (n) = 2T (n − 1)
35
The Master Theorem: Linear differences
NB
The Master Theorem applies to recurrences where T (n) is defined
in terms of T (n/b); not in terms of T (n − 1).
However, the following is a consequence of the Master Theorem:
Theorem
Suppose
T (n) = a · T (n − 1) + bnk
Then
O(nk+1 )
if a = 1
T (n) =
O(an ) if a > 1
36
Exercise
Exercise
n
Solve T (n) = 3n T
2 with T (1) = 1
37
