程序代写代做代考 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)

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

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

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

8 13 21 34 55 …

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

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

Tracing Recursive Fibonacci

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 …

Tower of Hanoi

Init FinAux

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

Tower of Hanoi: 
Recursive Solution

Init FinAux

Move n-1 disks from Init to Aux.

Tower of Hanoi: 
Recursive Solution

Init FinAux

Move n-1 disks from Init to Aux.
Then move the nth disk to Fin.

Tower of Hanoi: 
Recursive Solution

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.

Tower of Hanoi: 
Recursive Solution

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.

Tower Of Hanoi:
Recursive Algorithm

Init FinAux

Tracing Tower of Hanoi
Recursive Algorithm

http://vornlocher.de/tower.html

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

Does the bag contain a $2 coin?

Yes

+ $2

made from

Coin Change Problem:
Decomposition

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

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

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

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

Related Posts