程序代写代做代考 data structure algorithm 06.key

06.key

http://people.eng.unimelb.edu.au/tobym

@tobycmurray

toby.murray@unimelb.edu.au

DMD 8.17 (Level 8, Doug McDonell Bldg)

Toby Murray

COMP90038 

Algorithms and Complexity

Lecture 6: Recursion
(with thanks to Harald Søndergaard)

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

2

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

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

3

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

result: 1
n: 5
result: 5result: 20
n: 4n: 3
result: 60
n: 2
result: 120
n: 1n: 0

Iterative version
normally

preferred since it is
constant space

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Fibonacci Numbers
• To generate the nth number of sequence: 1 1 2 3 5

8 13 21 34 55 …

4

Follows the mathematical
definition of Fibonacci
numbers very closely.

Easy to understand

Basic operation: addition

Complexity is exponential in n

But performs lots of
redundant computation

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

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

items. Recursive version: left; iterative version: right

5

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).)

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tracing Recursive Fibonacci

6

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 1 2 3 5 8 …

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi

7

Init FinAux

Move n disks from Init to Fin. A larger disk can
never be placed on top of a smaller one.

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:

Recursive Solution

8

Init FinAux

Move n-1 disks from Init to Aux.

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:

Recursive Solution

9

Init FinAux

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

10

Init FinAux

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.

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower of Hanoi:

Recursive Solution

11

Init FinAux

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.

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tower Of Hanoi:
Recursive Algorithm

12

Init FinAux

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Tracing Tower of Hanoi
Recursive Algorithm

13

http://vornlocher.de/tower.html

http://vornlocher.de/tower.html

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

14

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Coin Change Problem:
Decomposition

15

$4

Does the bag contain a $2 coin?

Yes

+ $2

made from

made from

No

$4

made from

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Coin Change Problem:
Decomposition

16

The number of ways of making $4 is therefore:

1 x the number of
ways of making $2

the number of ways of
making $4 without

using a $2 coin

+

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Coin Change Problem: 

Partial Algorithm

17

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})

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

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

18

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Coin Change Problem:
Full Recursive Algorithm

19

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}). 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. • Its running time grows exponentially as you grow the input amount. • More efficient solutions can be developed using memoing or dynamic programming—more about that later (around Week 10). 20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Next Time… • Graphs, trees, graph traversal and allied algorithms. 21