代写 data structure algorithm html math graph COMP90038
 Algorithms and Complexity

COMP90038
 Algorithms and Complexity
Lecture 6: Recursion
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Recursion
We’ve already seen some examples

A very natural approach when the data structure is

recursive (e.g. lists, trees)
But also examples of naturally recursive array

processing algorithms

Next week we’ll express depth first graph traversal recursively (the natural way); later we’ll meet other examples of recursion too

Example: Factorial
n!: we can use recursion (left) or iteration (right)

F(5) =F(4)⋅5
= (F(3) ⋅ 4) ⋅ 5
= ((F(2) ⋅ 3) ⋅ 4) ⋅ 5
= (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= 120
n: 420315
result: 61521200
Iterative version normally preferred since it is constant space
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

4
Complexity is exponential in n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Fibonacci Numbers
Follows the mathematical definition of Fibonacci numbers very closely.
Easy to understand
But performs lots of redundant computation
To generate the nth number of sequence: 1 1 2 3 5

8 13 21 34 55 …
Basic operation: addition

Fibonacci Again
Of course we only need to remember the latest two

items. Recursive version: left; iterative version: right
Initial call: Fib(n, 1, 0) Time complexity of both
solutions is linear in n
(There is a cleverer, still recursive, way which is O(log n).)
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tracing Recursive Fibonacci
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Initial call: Fib(5, 1, 0)
Fib(5,1,0)
= Fib(4,1,1)
= Fib(3,2,1)
= Fib(2,3,2)
= Fib(1,5,3)
= Fib(0,8,5) =8
Fibonacci Sequence:
 1 12 3 5 8 …

Tower of Hanoi
Init Aux Fin
Move n disks from Init to Fin. A larger disk can never be placed on top of a smaller one.
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:
 Recursive Solution
Init Aux Fin Move n-1 disks from Init to Aux.
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:
 Recursive Solution
9
Init Aux Fin Move n-1 disks from Init to Aux.
Then move the nth disk to Fin.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:
 Recursive Solution
Init Aux Fin
Move n-1 disks from Init to Aux. Then move the nth disk to Fin. Then move the n-1 disks from Aux to Fin.
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:
 Recursive Solution
Init Aux Fin
Move n-1 disks from Init to Aux. Then move the nth disk to Fin. Then move the n-1 disks from Aux to Fin.
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower Of Hanoi: Recursive Algorithm
Init Aux Fin
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tracing Tower of Hanoi Recursive Algorithm
http://vornlocher.de/tower.html
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
A Challenge:

Coin Change Problem
There are 6 different kinds of Australian coin
In cents, their values are: 5, 10, 20, 50, 100, 200
In how many different ways can I produce a handful of coins adding up to $4?
This is not an easy problem!
• • •

Key to solving it is to find a way to break it down

into simpler sub-problems

Coin Change Problem:
Decomposition
$4 made from
Does the bag contain a $2 coin? Yes No
+
made from
$2 $4
made from
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Coin Change Problem: Decomposition
The number of ways of making $4 is therefore:
16
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1 x the number of ways of making $2
+
the number of ways of making $4 without using a $2 coin

Coin Change Problem:
 Partial Algorithm
function WAYS(amount, denominations) // … base cases ….
d ← selectLargest(denominations)

return WAYS(amount − d, denominations) +
WAYS(amount, denominations \ {d})
For example:
Ways(400, {5,10,20,50,100,200}) = Ways(200, {5,10,20,50,100,200}) +
 Ways(400, {5,10,20,50,100})
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

18
Coin Change Problem: Base Cases
Each time we recurse, we decrease either:
amount (by subtracting some quantity from it), or


demonisations (by removing an item from the set) •

Consider each of these separately.
amount base cases:
amount = 0: there is one way (using no coins)
amount < 0: there are no ways to make this denominations = ∅ (and amount > 0): 

there are no ways to make this amount Copyright University of Melbourne 2016, provided under Creative Commons Attribution License


• •

Coin Change Problem: Full Recursive Algorithm
function WAYS(amount, denominations)
 if amount = 0 then 

return 1

if amount < 0 then 
 return 0
 if denominations = ∅ then 
 return 0
 d ← selectLargest(denominations)
 return WAYS(amount − d, denominations) + WAYS(amount, denominations \ {d}) Initial call: WAYS(amount, {5, 10, 20, 50, 100, 200}). 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Recursive Solution and its
 Complexity Although our recursive algorithm is short and elegant, it is not the most efficient way of solving the problem. • • More efficient solutions can be developed using memoing or dynamic programming—more about that later (around Week 10). Its running time grows exponentially as you grow • the input amount. 21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Next Time... Graphs, trees, graph traversal and allied • algorithms.