CS1010S Programming Methodology
CS1010S Programming Methodology
Lecture 3
Recursion, Iteration &
Order of Growth
29 Aug 2018
Python Problems?
cs1010s-staff@googlegroups.com
0
10
20
30
40
50
60
1 2 3 4 5 6 R 7 8 9 10 11 12 13 14 15
Le
ve
l
Week
Expected Level Progression
Max Level
Typical Level
Minimum Level
M
id
te
rm
T
e
st
Week
1 2 3 4 5 6 R 7 8 9 10 11 12 13
Difficulty Curve
Reinforcements
Remedial classes
• Every week
• 6:30 – 8:30 pm
• Watch Coursemology for updates
Done with all the
missions?
Got a lot of time to burn?
Optional Trainings
Contests
Due 9 Sep 2018
Winning: 400 EXP + Prize
Participation: 50 EXP
Recap
Inputs Function Output
Don’t need to know how it works
Just know what it does
(the inputs
and output)
Learning Outcomes
After this lesson, you should be able to
• know how apply divide and conquer technique to solve a
problem
• differentiate what is recursion and iteration
• state the order of growth in terms of time and space for
computations
Divide
&
Conquer
Problem
Sub-
problem 1
Sub-
problem 2
Sub-sub
problem 3
Sub-sub
problem 4
Key Insight:
Smaller problems
are easier to solve
What is Recursion
Smaller child problem(s) has
same structure as the parent
A recursive function is
defined as itself
e.g. 𝑓 𝑛 = ⋯𝑓 𝑚 ⋯
Analogy
Your friend is late for lecture…
Caryn
last seen today at 10:10am
Eh where are you?
Ahh… I’m late! Trying to
catch a zulbat.
Pls help me chope seat. Tell
me which row and col ur at
10:10AM
How to find your row?
The Strategy
• Your row number is 1 more than the row in front of you.
• Ask the person in front for his/her row number and add 1 to it.
• The person in front uses the same strategy.
• Eventually, person in front row simply replies 1.
This is Recursion
Example
Consider the factorial function:
𝑛! = 𝑛 × 𝑛 − 1 × (𝑛 − 2)⋯× 1
Rewrite:
𝑛! = ቊ
𝑛 × 𝑛 − 1 ! , 𝑛 > 1
1 , 𝑛 ≤ 1
Factorial
𝑛! = ቊ
𝑛 × 𝑛 − 1 ! , 𝑛 > 1
1 , 𝑛 ≤ 1
def factorial(n):
if n <= 1: return 1 else: return n * factorial(n – 1) Recursion def factorial(n): if n <= 1: return 1 else: return n * factorial(n – 1) Function that calls itself is called a recursive function terminating condition recursive call Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 Note the build up of pending operations. Recursion n n - 1 computed with n - 2 computed with 2 computed with 1 computed with Terminating condition Answer is trivial How to write recursion 1. Figure out the base case - Typically n = 0 or n = 1 2. Assume you know how to solve n – 1 - Now how to solve for n? Factorial: Linear recursion def factorial(n): if n <= 1: return 1 else: return n * factorial(n – 1) factorial(4) factorial(3) factorial(2) factorial(1) Fibonacci Numbers Leonardo Pisano Fibonacci (12th century) is credited for the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, … Note: each number is the sum of the previous two. Fibonacci in Math 𝑓𝑖𝑏(𝑛) = ቐ 0, 𝑛 = 0 1, 𝑛 = 1 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1
Fibonacci in Python
𝑓𝑖𝑏(𝑛) = ቐ
0, 𝑛 = 0
1, 𝑛 = 1
𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1
def fib(n):
if (n == 0):
return 0
elif (n == 1):
return 1
else:
return fib(n – 1) + fib(n – 2)
Tree recursion
leaves
root
fib(5)
fib(4) fib(3)
fib(3) fib(2)
fib(1)
fib(2) fib(1)
fib(0) 1
1 0
fib(1) fib(0)
1 0
fib(2)
fib(1) fib(0)
fib(1)
1 0
1
Mutual recursion
def ping(n):
if (n == 0):
return n
else:
print(“Ping!”)
pong(n – 1)
def pong(n):
if (n == 0):
return n
else:
print(“Pong!”)
ping(n – 1)
ping(10)
Ping!
Pong!
Ping!
Pong!
Ping!
Pong!
Ping!
Pong!
Ping!
Pong!
Iteration
the act of repeating a process with the
aim of approaching a desired goal, target
or result.
– Wikipedia
Iterative Factorial
Idea
Start with 1, multiply by 2, multiply by 3, … , multiply by n.
𝑛! = 1 × 2 × 3⋯× 𝑛
Product
1 ×2624120
Counter
12345
Iterative Factorial
𝑛! = 1 × 2 × 3⋯× 𝑛
Computationally
Starting:
product = 1
counter = 1
Iterative (repeating) step:
product product × counter
counter counter + 1
End:
product contains the result
Iterative Factorial
Start with 1, multiply by 2, multiply by 3, …
𝑛! = 1 × 2 × 3⋯× 𝑛
Python Code
def factorial(n):
product, counter = 1, 1
while counter <= n:
product = product * counter
counter = counter + 1
return product
while loop
while
expression
• Predicate (condition) to stay within the loop
body
• Statement(s) that will be evaluated if predicate is True
Yet another way
𝑛! = 1 × 2 × 3⋯× 𝑛
Factorial rule:
product product × counter
counter counter + 1
def factorial(n):
product = 1
for counter in range(2, n+1):
product = product * counter
return product
non-inclusive.
Up to n.
for loop
for in
sequence
• a sequence of values
var
• variable that take each value in the sequence
body
• statement(s) that will be evaluated for each value in the sequence
range function
range([start,] stop[, step])
creates a sequence of integers
• from start (inclusive) to stop (non-inclusive)
• incremented by step
Examples
for i in range(10):
print(i)
for i in range(3, 10):
print(i)
for i in range(3, 10, 4):
print(i)
break & continue
for j in range(10):
print(j)
if j == 3:
break
print(“done”)
for j in range(10):
if j % 2 == 0:
continue
print(j)
print(“done”)
0
1
2
3
done
1
3
5
7
9
done
Break out
of loop
Continue with
next value
Iterative process
def factorial(n):
product, counter = 1, 1
while counter <= n:
product = (product *
counter)
counter = counter + 1
return product
factorial(6)
counter > n (7 > 6)
return product (720)
product counter
1 1
1 2
2 3
6 4
24 5
120 6
720 7
Recursion
vs
Iteration
Recursive process occurs when there
are deferred operations.
Iterative process does not have
deferred operations.
Recursive Process
factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2))
5 * (4 * (3 * (2 * factorial(1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120
deferred
operations
Orders of Growth
Like Physicists, we care about two
things:
1. Space
2. Time
Rough measure of resources
used by a computational process
Space: how much memory do we need to
run the program
Time: how long it takes to run a program
Order of growth
Why do we care?
We want to know how much
resource our algorithm needs
Analogy
Suppose you want to buy a Blu-ray movie
from Amazon (~40GB)
Two options:
1. Download
2. 2-day Prime Shipping
Which is faster?
Buying the Entire Series
What if you want more movies?
• 8 Blu-ray discs
• ~320 GB
Which is faster?
1. Download, or
2. 2-day delivery
Even more movies?
Download vs Delivery
# of movies
Time
Delivery2 days
Download
1 hour
We want to ask questions like:
factorial(5) → factorial(10) ?
fib(10) → fib(20)?
How much more time?
How much more space?
2x?
Same?
4x?
Order of Growth is NOT the absolute
time or space a program takes to run
Order of Growth is the proportion of
growth of the time/space of a
program w.r.t. the growth of the
input
Formal Definition
Let n denote size of the problem.
Let 𝑅 𝑛 denote the resources needed.
Definition:
𝑅 𝑛 has order of growth Θ(𝑓 𝑛 ) written
𝑅 𝑛 = Θ(𝑓 𝑛 )
If there are positive constants 𝑘1 and 𝑘2 such that
𝑘1𝑓 𝑛 ≤ 𝑅(𝑛) ≤ 𝑘2𝑓(𝑛)
for any sufficiently large value of 𝑛
Diagram
For 𝑛 >= 𝑛0, 𝑅(𝑛) is sandwiched between
O(𝑓(𝑛))
(𝑓(𝑛))
(𝑓(𝑛))
Some common 𝑓(𝑛)
• 1
• 𝑛
• 𝑛2
• 𝑛3
• log 𝑛
• 𝑛 log 𝑛
• 2𝑛
Intuitively
If 𝑛 is doubled
(i.e. increased to 2𝑛)
then 𝑅(𝑛)
(the resource required),
is increased to 𝑓(2𝑛)
Another analogy
• Suppose you can run 10 m in 1.5 secs
• Time is linear to distance
20 m
100 m
10 m
20 m
Shuttle Run
• Run and return
• Time is _______ to distance
10 m
Recap: Recursive Factorial
def factorial(n):
if n <= 1: return 1 else: return n * factorial(n – 1) Order of growth? 1. Time 2. Space Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 • Time #operations • Linearly proportional to n Recursive process factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 • Space #pending operations • Linearly proportional to n Recursive Factorial factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2)) 5 * (4 * (3 * (2 * factorial(1))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120 Time: O(𝑛) Space: O(𝑛) Linear Linear Iterative Factorial def factorial(n): product, counter = 1, 1 while counter <= n: product = (product * counter) counter = counter + 1 return product factorial(6) product counter 1 1 1 2 2 3 6 4 24 5 120 6 720 7 Iterative process Time (# of steps): • linearly proportional to n Space (memory): • constant • no deferred operations • All information contained in 2 variables (old values overwritten by new) Time: O(𝑛) Space: O(1) Linear Constant product: counter: 1 1 1 2 2 3 6 4 24 5 120 6 720 7 Recap: Fibonacci 𝑓𝑖𝑏(𝑛) = ቐ 0, 𝑛 = 0 1, 𝑛 = 1 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏(𝑛 − 2) 𝑛 > 1
def fib(n):
if (n == 0):
return 0
elif (n == 1):
return 1
else:
return fib(n – 1) + fib(n – 2)
Tree recursion
leaves
root
fib(5)
fib(4) fib(3)
fib(3) fib(2)
fib(1)
fib(2) fib(1)
fib(0) 1
1 0
fib(1) fib(0)
1 0
fib(2)
fib(1) fib(0)
fib(1)
1 0
1
Fibonacci
• Number of leaves in tree is 𝑓𝑖𝑏(𝑛 + 1)
• Can be shown that fib(n) is the closest integer to
Φ𝑛
5
– Where Φ =
1+ 5
2
≈ 1.6180
– called the golden ratio
• Therefore time taken is ≈ Φ𝑛
– (exponential in n)
Tree recursion
• Time:
– Proportional to number of leaves, i.e.,
exponential in n.
• Space (memory):
– Proportional to the depth of the tree, i.e.,
linear in n.
General form
Suppose a computation 𝐶 takes 3𝑛 + 5 steps
to complete, what is the order of growth?
O(3𝑛 + 5) = O(𝑛)
Take the largest term.
Drop the constants.
Another Example
How about 3𝑛 + 4𝑛2 + 4?
Order of growth
= O 3𝑛 + 4𝑛2 + 4
= O(3𝑛)
Tips
• Identify dominant terms, ignore smaller terms
• Ignore additive or multiplicative constants
– 4𝑛2 – 1000𝑛 + 300000 = O(𝑛2)
–
𝑛
7
+ 200𝑛 log 𝑛 = O(𝑛 log 𝑛)
• Note: log𝑎 𝑏 =
log𝑐 𝑏
log𝑐 𝑎
– So base is not important
More tricks in CS1231,
CS3230
Some involve sophisticated proofs
For now…
Count the number of “basic computational
steps”.
– Identify the basic computation steps
– Try a few small values of n
– Extrapolate for really large n
– Look for “worst case” scenario
Numeric example
13.7 billion years ≈ 259 seconds
?
1
2
3
10
20
30
100
200
300
1000
2000
3000
106
𝑛
13.8
0
0.69
1.098
2.3
2.99
3.4
4.6
5.29
5.7
6.9
7.6
8
log 𝑛
13.8 × 10
0
1.38
3.29
23.0
59.9
109
461
1060
1710
6910
15200
24019
6
𝑛 log 𝑛
10
1
4
9
100
400
900
10000
40000
90000
106
4 × 106
9 × 106
12
𝑛2
10
1
8
27
1000
8000
27000
106
8 × 106
27 × 106
109
8 × 109
27 × 109
18
𝑛3
2
4
8
1024
106
109
1.2 × 1030
1.6 × 1060
2.03 × 1090
1.07 × 10301
?
?
2𝑛
Time: how long it takes to run a program
Space: how much memory do we need to
run the program
pythontutor.com
itoday.com
Moral of the story
Different ways of performing a
computation (algorithms) can consume
dramatically different amounts of
resources.
Recursion Revisited
• Solve the problem for a simple (base) case
• Express (divide) a problem into one or more
smaller similar problems
• Similar to
Mathematical Induction
Comparison
Mathematical Induction
•Start with a base case 𝑏
•Assume 𝑘 works, derive a
function to show 𝑘 + 1 also
works
•Therefore, it must be true for
all cases ≥ 𝑏
Recursion
•Find base case(s) b where we
can just state the answer
•Derive a function to express
the problem of size n as sub-
problems of 𝑘 < 𝑛
•The function can therefore
solve all 𝑛 ≥ 𝑏
Sometimes it may be possible that you
will need more than one base case?
When? Why?
Tree recursion
fib(5)
fib(4) fib(3)
fib(3) fib(2)
fib(1)
fib(2) fib(1)
fib(0) 1
1 0
fib(1) fib(0)
1 0
fib(2)
fib(1) fib(0)
fib(1)
1 0
1
Other times you may have to express a
problem in another form and the other form
back in the present form
(mutual recursion)
- E.g. sin and cos
More Examples
Greatest Common Divisor
The 𝐺𝐶𝐷 of two numbers 𝑎 and 𝑏, is the largest
positive integer that divides both 𝑎 and 𝑏 without
remainder.
Greatest Common Divisor
Naïve Algorithm:
Given two numbers 𝑎 and 𝑏
Start with 1.
Check if it divides both 𝑎 and 𝑏.
Try 2, then 3, and so on… until you reach 𝑎 or 𝑏.
Greatest Common Divisor
Euclid’s Algorithm:
Given two numbers 𝑎 and 𝑏, where 𝑎 = 𝑏 ∙ 𝑄 +
𝑟 (the remainder of the division), then we have
𝐺𝐶𝐷 𝑎, 𝑏 = 𝐺𝐶𝐷 𝑏, 𝑟 , ∀𝑎, 𝑏 > 0
𝐺𝐶𝐷(𝑎, 0) = 𝑎
Greatest Common Divisor
def gcd(a, b):
if (b == 0):
return a
else:
return gcd(b, a % b)
GCD(206,40) = GCD(40,6)
= GCD(6,4)
= GCD(4,2)
= GCD(2,0)
= 2
𝐺𝐶𝐷(𝑎, 𝑏) = 𝐺𝐶𝐷(𝑏, 𝑟), ∀ 𝑎, 𝑏 > 0
𝐺𝐶𝐷(𝑎, 0) = 𝑎
Tower of Hanoi
Towers of Hanoi
Goal: Move all discs from one stick to another
Rules:
1. Can only move one disc at a time
2. Cannot put a larger disc over a smaller disc
Towers of Hanoi
Goal: Move all discs from one stick to another
Rules:
1. Can only move one disc at a time
2. Cannot put a larger disc over a smaller disc
Towers of Hanoi
Suppose we know how to move 3
discs from A to C
A B C
Towers of Hanoi
Suppose we know how to move 3
discs from A to C
A B C
Towers of Hanoi
Claim: we can move 3 discs from
A to B. Why?
A B C
Towers of Hanoi
Claim: we can move 3 discs from
A to B. Why?
A B C
Towers of Hanoi
How to move 4 discs from A to C?
A B C
Towers of Hanoi
How to move 4 discs from A to C?
• Move 3 disc from A to B
A B C
Towers of Hanoi
How to move 4 discs from A to C?
• Move 3 disc from A to B
• Move 1 disc from A to C
A B C
Towers of Hanoi
How to move 4 discs from A to C?
• Move 3 disc from A to B
• Move 1 disc from A to C
• Move 3 disc from B to C
A B C
Divided into smaller problem
• Move 4 discs
• Move 5 discs?
• Move 𝑛 discs?
→Move 3 discs
→Move 4 discs
→Move 𝑛 − 1
discs
Recursion
1. Expressed (divided) the problem into one
or more smaller problems
𝑛 = 𝑓(𝑛 − 1)
2. Solve the simple (base) case
– 1 disc?
– 0 disc? Move directly from X to Y
Do nothing
High Level Idea
To move 𝑛 discs from A to C using B
A B C
…
𝑛
High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C
A B C
…
High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C
2. move disc from A to C
A B C
…
High Level Idea
To move 𝑛 discs from A to C using B
1. move 𝑛 − 1 discs from A to B using C
2. move disc from A to C
3. move 𝑛 − 1 discs from B to C using A
A B C
…
Towers of Hanoi
def move_tower(size, src, dest, aux):
if size == 1:
print_move(src, dest) # display the move
else:
move_tower(size-1, src, aux, dest)
print_move(src, dest)
move_tower(size-1, aux, dest, src)
src aux dest
Tower of Hanoi
def print_move(src, dest):
print(“move top disk from “, src” to “, dest)
Another example
What does this function compute?
def foo(x, y):
if (y == 0):
return 1
else:
return x * foo(x, y-1)
This?
def power(b, e):
if (e == 0):
return 1
else:
return b * power(b, e-1)
Exponentiation (𝑏𝑒)
def power(b, e):
if (e == 0):
return 1
else:
return b * power(b, e-1)
• Time requirement?
• Space requirement?
Can we do better?
O(𝑛)
O(𝑛)
Another way to express 𝑏𝑒
𝑏𝑒 = ൞
1, 𝑒 = 0
(𝑏2)
𝑒
2, 𝑒 is even
𝑏𝑒−1 ∙ 𝑏, 𝑒 is odd
Fast Exponentiation
def fast_expt(b, e):
if e == 0:
return 1
elif e % 2 == 0:
return fast_expt(b*b, e/2)
else:
return b * fast_expt(b, e-1)
• Time requirement?
• Space requirement?
Can we do this iteratively?
O(log 𝑛)
O(log 𝑛)
𝑏𝑒 = ൞
1, 𝑒 = 0
(𝑏2)
𝑒
2, 𝑒 is even
𝑏𝑒−1 ∙ 𝑏, 𝑒 is odd
Summary
• Recursion
– Solve the problem for a simple (base) case
– Express (divide) a problem into one or more smaller
similar problems
• Iteration: while and for loops
Summary
• Order of growth:
– Time and space requirements for
computations
– Different ways of performing a computation
(algorithms) can consume dramatically
different amounts of resources.
– Pay attention to efficiency!
Something to think about….
• Can you write a recursive function
sum_of_digits that will return the sum of digits of
an arbitrary positive integer?
• How about a recursive function
product_of_digits that will return the product of
the digits?
Notice a pattern?
How would you write a function that
computed the sum of square roots of
the digits of a number?
Why is Python Cool?
Ask your friends in CS1010 how they
would solve these problems in C.