FIND A SOLUTION AT Academic Writers Bay

Theory and Practice of Artificial Intelligence

Recursion, Examples and Exercises

Daniel Polani

School of Physics, Engineering and Computer Science

University of Hertfordshire

March 1, 2021

All rights reserved. Permission is granted to copy and distribute these slides in full or in part for purposes of

research, education as well as private use, provided that author, affiliation and this notice is retained.

Use as part of home- and coursework is only allowed with express permission by the responsible tutor and, in

this case, is to be appropriately referenced.

Theory and Practice of Artificial Intelligence 20 / 142

Exercise 2

Assumptions

Consider the tower of Hanoi

problem with three poles and

n disks.

Task

Write a function hanoi(.)

that moves a tower of size n

from a given start pole to a

target pole.

Theory and Practice of Artificial Intelligence 21 / 142

Exercise 3

Assumptions

Consider the tower of Hanoi

problem with three poles and

n disks.

Task

Write a function hanoi(.)

that moves a tower of size n

from a given start pole to a

target pole.

Example

def hanoi(n, start, goal, ignore):

if n == 1:

print start, “->”, goal

return

hanoi(n-1, start, ignore, goal)

print start, “->”, goal

hanoi(n-1, ignore, goal, start)

hanoi(4, 1, 2, 3)

Theory and Practice of Artificial Intelligence 21 / 142

Stateful Functions” (Generators and Yields)

Functions: information processing, then return result

a new call, new variables, new results

Generators: information processing, then yield result

new call to generator retains old state and

continues with new results

Example

def colours():

yield “red”

yield “green”

yield “black”

for c in colours():

print c

Example

def colours():

for c in [“red”,”green”,”black”]:

yield c

for c in colours():

print c

Theory and Practice of Artificial Intelligence 22 / 142

Exercise 4 (Permutation)

Assumptions

Consider a list […]

of elements.

Task

Write a generator

perm(.) that produces

all permutations of

above list.

Theory and Practice of Artificial Intelligence 23 / 142

Exercise 5 (Permutation)

Assumptions

Consider a list […]

of elements.

Task

Write a generator

perm(.) that produces

all permutations of

above list.

Example (Wrong! | Why?)

def insertion(e, s):

for i in range(len(s)+1):

s[i:i] = [e]

yield s

def perm(s):

if s == []:

yield []

else:

e, s1 = s[0], s[1:]

for s1p in perm(s1):

for p in insertion(e,s1p):

yield p

for p in perm([1,2,3,4]): print p

Theory and Practice of Artificial Intelligence 23 / 142

Exercise 6 (Permutation)

Assumptions

Example (Right! | Why?)

Consider a list […]

of elements.

Task

Write a generator

perm(.) that produces

all permutations of

above list.

def insertion(e, s):

for i in range(len(s)+1):

yield s[:i] + [e] + s[i:]

def perm(s):

if s == []:

yield []

else:

e, s1 = s[0], s[1:]

for s1p in perm(s1):

for p in insertion(e,s1p):

yield p

for p in perm([1,2,3,4]): print p

Theory and Practice of Artificial Intelligence 24 / 142

Copying Lists

Warning: Applying Functions to Lists

Functions/generators can modify lists destructively!

Example

def modifier(s):

s[2:4] = [“foo”, “bar”]

s = [1,2,3,4,5,6]

print “before:”, s

modifier(s)

print “after:”, s

# [1,2,3,4,5,6]

# [1,2,’foo’,’bar’,5,6]

Theory and Practice of Artificial Intelligence 25 / 142

Copying Lists

Warning: Applying Functions to Lists

Functions/generators can modify lists destructively!

Example

def modifier(s):

s[2:4] = [“foo”, “bar”]

s = [1,2,3,4,5,6]

print “before:”, s

modifier(s)

print “after:”, s

# [1,2,3,4,5,6]

# [1,2,’foo’,’bar’,5,6]

Example

def modifier(s):

s = s[:]

s[2:4] = [“foo”, “bar”]

s = [1,2,3,4,5,6]

print “before:”, s

modifier(s)

print “after:”, s

# [1,2,3,4,5,6]

# [1,2,3,4,5,6]

Theory and Practice of Artificial Intelligence 25 / 142

Proof of Correctness I

Question

How do you demonstrate that

1 you get all permutations?

2 you get each permutation exactly once?

Sanity Check

How many resulting permutations?

n! is a good start | it does not guarantee correctness, but if

this is wrong, that needs fixing first.

Theory and Practice of Artificial Intelligence 26 / 142

Proof of Correctness II

Induction

show that base case is correct (this is trivial)

assume that permutation generator for the smaller list (length

n – 1) is correct, i.e. that

1 it generates all permutations

2 all of them exactly once

under this assumption, prove that full list permutation (n)

retains this property.

Theory and Practice of Artificial Intelligence 27 / 142

Proof of Correctness III

Proof Idea

Base Case: obvious. Empty list has only itself as

permutation. Done.

Note: Not talking about debugging, only want to know whether recursion step covers

everything

Recursion Step: 1 Do we get all?

Assume, some arbitrary permutation given.

Is it included? We covered the case of the

empty list, so assume the list is not empty.

Recursion says: we know it is correct for list

of shorter length n – 1.

What now?

2 Do we get all of them exactly once?

Theory and Practice of Artificial Intelligence 28 / 142

Sheep and Cow Problem

Solution Part 1

E = 0

C = 1

S = 2

start_stable = [C, C, C, C, E, S, S, S, S]

goal_stable = [S, S, S, S, E, C, C, C, C]

Theory and Practice of Artificial Intelligence 29 / 142

Sheep and Cow Problem | Considerations

Possible Moves

1 Cow moves one field to the right (if empty)

2 Sheep moves one field to the left (if empty)

3 Cow jumps over one Sheep into an empty field

4 Sheep jumps over one Cow into an empty field

Theory and Practice of Artificial Intelligence 30 / 142

Sheep and Cow Problem | Considerations II

Patterns of Possible Moves

Cow moves right:

….C_….

…._C….

Sheep moves left:

…._S….

….S_….

Cow jumps right:

….CS_…

…._SC….

Sheep jumps left:

…._CS….

….SC_….

Idea

1 can only jump into empty

field

2 identify candidates for

moving/jumping animal

3 need to be inside field

4 need to conform to one of

the given patterns

Theory and Practice of Artificial Intelligence 31 / 142

Sheep and Cow Problem

Solution Part 2

def successors(stable):

# find empty spot

empty = stable.index(E)

# generate list of unfiltered candidate positions

candidates = [empty-2, empty-1, empty+1, empty+2]

# keep only those which are inside the stable

candidates = [c for c in candidates if c >= 0 and c < len(stable)]

# Cows can always move right, Sheep always left, and from two fields

# apart, they have to jump over an opposite animal

candidates = [c for c in candidates if

stable[c:c+2] == [C, E] or # cow can move right

stable[c-1:c+1] == [E, S] or # sheep can move left

stable[c:c+3] == [C, S, E] or # cow jumps over sheep

stable[c-2:c+1] == [E, C, S]] # sheep jumps over cow

# make sure that all these entries are occupied

# (not necessary for operation, just better style)

assert not [c for c in candidates if stable[c] == E]

for c in candidates:

new_stable = stable[:] # make a copy

# move the candidate into empty pos

new_stable[c], new_stable[empty] = new_stable[empty], new_stable[c]

yield new_stable # remember where we were

Theory and Practice of Artificial Intelligence 32 / 142

Sheep and Cow Problem

Solution Part 3

def solution(stable):

if stable == goal_stable:

return [stable]

# else, depth first

for new_stable in successors(stable):

# print new_stable

sol = solution(new_stable)

if sol:

return [stable] + sol

for s in solution(start_stable):

print s

Theory and Practice of Artificial Intelligence 33 / 142

- Assignment status: Already Solved By Our Experts
*(USA, AUS, UK & CA PhD. Writers)***CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS**

QUALITY: 100% ORIGINAL PAPER – **NO PLAGIARISM** – CUSTOM PAPER