Title arial bold 28pt
Dr. Adrian Euler
adrian. .uk
Lecture 5
Recursion and Data Processing
SMM283
Introduction to Python
www.cass.city.ac.uk
RECURSION
www.cass.city.ac.uk
A Recursive Power Function
Recursive function invokes/calls itself
Successive calls reduce to simpler task
Until base case with trivial solution reached
The nth power of a number
Iteratively
Recursively
www.cass.city.ac.uk
A Recursive Power Function
Example: Definition uses an iterative vs recursive solutions
www.cass.city.ac.uk
A Recursive factorial Function
Example: Definition uses the recursive definition of a factorial function.
www.cass.city.ac.uk
A Recursive Power Function
Traits of recursive algorithms
One or more base cases with direct solutions.
An “inductive step”
Reducing the problem to one or more smaller versions of the same problem
Reduction eventually culminating in a base case.
Called the reducing step.
www.cass.city.ac.uk
A Recursive Power Function
FIGURE: The recursive computation of power(2, 3).
www.cass.city.ac.uk
Recursive Palindrome Function
Sometimes a recursive solution is easier to understand and code than iterative routine.
Example(see next page for coding): Function uses recursion to determine whether or not word is a palindrome.
A palindrome is a word, phrase, number or sequence of words that reads the same backwards as forwards.
www.cass.city.ac.uk
Recursive Palindrome Function
www.cass.city.ac.uk
More on LISTS
www.cass.city.ac.uk
The list Object
A list is an ordered sequence of Python objects
Objects can be of any type
Objects do not have to all be the same type.
Constructed by writing items enclosed in square brackets … items separated by commas.
www.cass.city.ac.uk
The list Object
Table: List operations (The lists team, num, and words given in previous slide)
www.cass.city.ac.uk
The list Object
Table: List operations (The lists team, num, and words given in previous slide)
www.cass.city.ac.uk
Slices
A slice of a list is a sublist specified with colon notation
Analogous to a slice of a string
Table: Meanings of slice notations
www.cass.city.ac.uk
Slices
Table: Examples of slices where
list1 = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’].
www.cass.city.ac.uk
The split and join Methods
Split method turns single string into list of substrings
Join method turns a list of strings into a single string.
Notice that these methods are inverses of each other
www.cass.city.ac.uk
The split and join Methods
Example: These statements each display list [‘a’, ‘b’, ‘c’].
www.cass.city.ac.uk
The split and join Methods
Example: Program shows how join method used to display items from list of strings.
www.cass.city.ac.uk
Text Files
Text file is a simple file consisting of lines of text with no formatting
Text file can be created with any word processor
Python program can access the values
www.cass.city.ac.uk
Text Files
Given
Program opens for reading a file of text
Strips newline characters
Characters placed into a list
www.cass.city.ac.uk
Text Files
Furthermore
Suppose data is all numbers,
Previous code produces list of strings, each a number
Place the numbers into a list with this code
www.cass.city.ac.uk
TUPLES
www.cass.city.ac.uk
The tuple Object
Tuples, like lists, are ordered sequences of items
Difference – tuples cannot be modified in place
Have no append, extend, or insert method
Items of tuple cannot be directly deleted, sorted, or altered
www.cass.city.ac.uk
The tuple Object
All other list functions and methods apply
Items can be accessed by indices
Tuples can be sliced, concatenated, and repeated
Tuples written as comma-separated sequences enclosed in parentheses
Can also be written without the parentheses.
www.cass.city.ac.uk
The tuple Object
Example: Program shows tuples have several of same functions as lists.
www.cass.city.ac.uk
The tuple Object
Example: Program swaps values of two variables
www.cass.city.ac.uk
Nested Lists
Beside numbers or strings, items can be lists or tuples.
Consider a list of tuples named L
L[0] is the first tuple
L[0][0] is the first item in the first tuple
And L[-1] is the last tuple
L[-1][-1] is the last item in the last tuple
www.cass.city.ac.uk
Immutable and Mutable Objects
An object is an entity
Holds data.
Has operations and/or methods that can manipulate the data.
When variable created with assignment statement
Value on the right side becomes an object in memory
Variable references (points to) object
www.cass.city.ac.uk
Immutable and Mutable Objects
When list altered
Changes made to the object in list’s memory location
Contrast when value of variable is number, string, or tuple … when value changed,
Python designates a new memory location to hold the new value
And the variable references that new object
www.cass.city.ac.uk
Immutable and Mutable Objects
Another way to say this
Lists can be changed in place
Numbers, strings, and tuples cannot
Objects changed in place are mutable
Objects that cannot be changed in place are immutable
www.cass.city.ac.uk
Immutable and Mutable Objects
FIGURE: Memory allocation corresponding to a program.
www.cass.city.ac.uk
Immutable and Mutable Objects
FIGURE: Memory allocation corresponding to a program.
www.cass.city.ac.uk
Copying Lists
Consider results of this program
All because lists are mutable
www.cass.city.ac.uk
Copying Lists
Now note change in line 2
Third line of code will not affect memory location pointed to by list1
www.cass.city.ac.uk
Indexing, Deleting, and
Slicing Out of Bounds
Python does not allow out of bounds indexing for individual items in lists and tuples
But does allow it for slices
Given list1 = [1, 2, 3, 4, 5]
Then print(list1[7])
print(list1[-7])
del list1[7]
www.cass.city.ac.uk
Indexing, Deleting, and
Slicing Out of Bounds
If left index in slice too far negative
Slice will start at the beginning of the list
If right index is too large,
Slice will go to the end of the list.
www.cass.city.ac.uk
DICTIONARIES
www.cass.city.ac.uk
Dictionaries
Consider this function
A mini English-Spanish
dictionary
A function of this type is called a mapping
Python has an efficient and flexible mapping device, called a dictionary
The value of translate[“blue”] is “aloz”
www.cass.city.ac.uk
Dictionaries
Python dictionary is defined as
A collection of comma separated pairs
Of the form ”key:value”
Enclosed in curly braces.
Value associated with key1 is given by the expression dictionaryName[key1].
www.cass.city.ac.uk
Dictionaries
Example
Table: Dictionary Operations
www.cass.city.ac.uk
Dictionaries
Table 4 Dictionary Operations
www.cass.city.ac.uk
Dictionaries
Table 4 Dictionary Operations
www.cass.city.ac.uk
The dict Function
List of 2-item lists or 2-item tuples can be converted to a dictionary with dict function
Example
www.cass.city.ac.uk
Extracting Ordered Data from a Dictionary
A dictionary is an unordered structure
Does not have a sort method
However, items of dictionary can be placed into a list
As 2-tuples
In customized order
Use function of the form
www.cass.city.ac.uk
Dictionary Comprehension
Dictionaries can be created with dictionary comprehension.
Example
www.cass.city.ac.uk
EXCEPTIONS
www.cass.city.ac.uk
Exceptions
Exceptions occur due to circumstances beyond programmer’s control
Invalid data are input
File cannot be accessed
Even though might be user’s fault
Programmer must anticipate
Include code to work around the occurrence
www.cass.city.ac.uk
Exceptions
Table: Some Common Exceptions
www.cass.city.ac.uk
Exceptions
Table: Some Common Exceptions
www.cass.city.ac.uk
Exceptions
Sample problem:
Entry may be non numeric or just
Python gives following error message
www.cass.city.ac.uk
The try Statement
Robust program explicitly handles previous exception
Protecting the code with a try statement.
www.cass.city.ac.uk
The try Statement
Three types of except clauses:
www.cass.city.ac.uk
The try Statement
Example: Program with different assumptions
www.cass.city.ac.uk
The try Statement
Example 1:
www.cass.city.ac.uk
The try Statement
Example: Program uses exception handling to guarantee proper response from user.
www.cass.city.ac.uk
The else and finally Clauses
try statement also can include a single else clause
Follows the except clauses
Executed when no exceptions occur
try statement can end with a finally clause
Usually used to clean up resources such as files that were left open
try statement must contain either an except clause or a finally clause.
www.cass.city.ac.uk
The else and finally Clauses
Example: Program attempts to find the average and total of the numbers in a file.
www.cass.city.ac.uk
The else and finally Clauses
Example:
www.cass.city.ac.uk
READING THIS WEEK
Lecturer notes, which map to
SCHNEIDER, I. D., (2015), An Introduction to Programming Using Python, Global Edition
Chapter 2(section on lists, tuples and dictionaries) & chapter 5 (section dictionaries, and
chapter 6 (section on exceptions)
Additional Resources
Python Tutorial:
http://docs.python.org/tut/
59
www.cass.city.ac.uk
HOMEWORK THIS WEEK and next week
Complete Mock Tests 1 & 2.
Exercise 1. Write a recursive version of the function reverse(s), which reverses the string s in place.
Exercise 2. Write a user-defined function double mean(x = []) so that it computes the mean in a recursive way. Additionally you can try to apply recursion of the other functions of seminar 3 & 4 as well as the mocks 1& 2, as a way to gain more confidence on its use.
60
www.cass.city.ac.uk
60