1

COMP1117B Tutorial 10

map, filter and lambda

RECURSION
 2
About this tutorial

 Check your understanding

 Confusing concepts / common mistakes
 Revision on recursion
 Hints to tutorial exercises
 3
Q1

 What is the output of the following program?

A. Error
B. Address of m1
C. [-2, -3]
D. [False, True, True, False, False]
 4
Q1

 What is the output of the following program?

map(f1, L1) applies function f1

to each item of L1:
• f1(1) returns False
• f1(-2) returns True
• f1(-3) returns True
• f1(4) returns False
• f1(5) returns False
A. Error Note that map returns a map
B. Address of m1 object of the results, we need
to convert it to say, a list, to
C. [-2, -3] print it out.

D. [False, True, True, False, False]

 5
Q2

 What is the output of the following program?

A. Error
B. Address of m2
C. [1, -2, -3]
D. [True, True, True, False, False]
 6
Q2

 What is the output of the following program?

The filter() function takes in a function

and a sequence (e.g. list, set, tuple) as
arguments and filter out all the
elements for which the function returns
True.
A. Error
The filter() function returns an iterator.
B. Address of m2
C. [1, -2, -3]
D. [True, True, True, False, False]
 7
Q3

 What is the output of the following program?

A. Error
B. Address of m3
C. [-4, 8]
D. None of the above
 8
Q3

 What is the output of the following program?

A. Error
B. Address of m3
C. [-4, 8]
D. None of the above
 9
Q4

 What is the output of the following program?

A. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
B. [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
C. [0, 4, 16, 36, 64]
D. Error
 10
Q4

 What is the output of the following program?

0, 4, 16, 36, 64 0, 2, 4, 6, 8 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

A. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
B. [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
C. [0, 4, 16, 36, 64]
D. Error
 11
Q5

 What is the output of the following program?

A. 98
B. 99
C. 100
D. Infinite loop
 12
Q5

 What is the output of the following program?

A. 98
B. 99
C. 100
D. Infinite loop
 13
Tutorial Exercise 10.1
 14
Iterative vs Recursive

 Consider the factorial problem

 Iterative approach:
 4! = 4 x 3 x 2 x 1

i result * i result
 Compute this using a for loop
4 1*4 4
3 4*3 12
2 12*2 24
1 24*1 24
0 stop
 15
Iterative vs Recursive

 Consider the factorial problem

Recursive call
 Recursive approach:
 4! = 4 x 3!
= 4 x (3 x 2!)
= 4 x (3 x (2 x 1!))
= 4 x (3 x (2 x (1 x 0!)))
= 4 x (3 x (2 x (1 x 1)))

 Compute this using a recursive function.

 16
How to write a recursive function?

 Recursive approach:
 4! = 4 x 3!
= 4 x (3 x 2!) Recursive call
= 4 x (3 x (2 x 1!))
= 4 x (3 x (2 x (1 x 0!)))
= 4 x (3 x (2 x (1 x 1)))

 Divide the main problem into sub-problems of the same type.

 Main problem: finding 4!
 Sub-problems of the same type: finding 3!, 2!, 1!, 0!
 17
How to write a recursive function?

 Recursive approach:
 4! = 4 x 3!
= 4 x (3 x 2!) Recursive call
= 4 x (3 x (2 x 1!))
= 4 x (3 x (2 x (1 x 0!)))
= 4 x (3 x (2 x (1 x 1)))

 Step 1: define the base case(s)

 Base case(s): no further break down of sub-problem.
 18
How to write a recursive function?

 Recursive approach:
 4! = 4 x 3!
= 4 x (3 x 2!) Recursive call
= 4 x (3 x (2 x 1!))
= 4 x (3 x (2 x (1 x 0!)))
= 4 x (3 x (2 x (1 x 1)))

 Step 2: formulate the recursive case(s)

 recursive case(s): n! = n x (n - 1)!
 19
Tutorial Exercise 10.2
 20
Tutorial Exercise 10.2

Base case 1 Base case 2 Recursive case

 21
Tutorial Exercise 10.2

Base case 1

Base case 2

Recursive case
 22
Tutorial Exercise 10.3
 23
Tutorial Exercise 10.3

Base case
Recursive case 1
Recursive case 2
 24
Tutorial Exercise 10.3

Base case

Recursive case 1

Recursive case 2
 25
Tutorial Exercise 10.4
 26
Understanding Base Conversion

 Convert the number n = 56 to base b = 4

56 // 4 4 56 result = ""
4 14 …0 56 % 4 result = "0"
14 // 4
4 3 …2 14 % 4 result = "20"
result = "320"

 The number in base 4 is 320.

 27
Base Conversion (Recursive)

 Convert the number n = 56 to base b = 4

56 // 4 4 56 result = ""
4 14 …0 56 % 4 result = "0"
14 // 4
4 3 …2 14 % 4 result = "20"
result = "320"
Base case:
Recursive case: If n < b:
convert_base(n//b, b) return str(n) How to combine the result:
convert_base(n//b, b) + str(n % b)
 The number in base 4 is 320.
 28
Understanding Base Conversion

 Convert the number n = 56 to base b = 4

56 // 4 4 56 result = ""
4 14 …0 56 % 4 result = "0"
14 // 4
4 3 …2 14 % 4 result = "20"
result = "320"

def convert_base(n, b): Problem:

if n < b: str() only works for base 2 to 10
return str(n)
else:
return convert_base(n // b, b) + str(n % b)
 29
What about base > 10

 We need to convert:
 10 → A
 11 → B
 12 → C
 13 → D
 14 → E
 15 → F
 Hint:
 numStr = "0123456789ABCDEF".
 numstr[14] will give you "E".
 Use numStr instead of str().
 30
Q&A

 Please feel free to post on Moodle Forum if you

have questions.

 But don’t copy and paste your own code to the

Moodle forum.