$30
ITI 1120
Lab # 11
Recursion
1
Star.ng Lab 11
• Open a browser and log into Blackboard Learn
• On the le> hand side under Labs tab, find lab11 material
contained in lab11-students.zip file
• Download that file to the Desktop and unzip it.
2
Before star.ng, always make sure
you are running Python 3
This slide is applicable to all labs, exercises, assignments … etc
ALWAYS MAKE SURE FIRST that you are running Python 3.4 (3.5 is
fine too)
That is, when you click on IDLE (or start python any other way)
look at the first line that the Python shell displays. It should say
Python 3.4 or 3.5 (and then some extra digits)
If you do not know how to do this, read the material provided
with Lab 1. It explains it step by step
3
4
Later on if you wish, you can type them
into a computer (or copy/paste from the
solu.ons once I poste them)
Do all the exercises labeled as
Task in your head i.e. on a
paper
Task 1: (a) What do the following two programs print?
(b) What do func.ons orange and guave do when called with posi.ve integer as
input argument? (answer in plain language)
(c) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy both programs into Python Vizualizer. Make sure you
understand all the func.ons that are running (at the same .me) as you step through
the execu.on of the program.
Task 2:
(a) What does the following program print?
(b) Write one sentence that describes abstractly (in plain English) what the func.on mulberry
does when called with posi.ve integer as input argument.
(c) What would happen if we made mulberry(-3) call in the main, instead of mulberry (5)?
(d) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy code below into Python Vizualizer. Make sure you understand how
the program is running and what it is doing as you step through its execu.on of the program.
(e) What is the maximum number of mulberry func.ons running at any one .me, i.e. what is
the maximum number mulberry func.ons on the stack at any one .me?
- What is the answer for general n?
- Make the call mulberry(1000) in Python shell instead mulberry(4) of and observe what
happened? Why did that happen?
Task 3:
(a) What does the following program print?
(b) Write one sentence that describes abstractly (in plain English) what the func.on
cantaloupe does when called with posi.ve integer as input argument.
(c) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy code below into Python Vizualizer. Make sure you
understand how the program is running and what it is doing as you step through the
execu.on of the program.
(d) What is the maximum number of cantaloupe func.ons running at any one .me,
i.e. what is the maximum number cantaloupe func.ons on the stack at any one .me?
What is the answer for general n?
Task 4:
(a) What does the following program print?
(b) Write one sentence that describes abstractly (in plain English) what the func.on
almond does given a list of numbers lst as input argument?
(c) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy code below into Python Vizualizer. Make sure you
understand how the program is running and what it is doing as you step through the
execu.on of the program.
Task 5:
(a) What does the following program print?
(b) Write one sentence that describes abstractly (in plain English) what the func.on
fig does given a list of numbers lst as input argument and high=len(lst)-1.
(c) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy code below into Python Vizualizer. Make sure you
understand how the program is running and what it is doing as you step through the
execu.on of the program.
Task 6:
(a) What does the following program print?
(b) Write one sentence that describes abstractly (in plain English) what the func.on
almond does (given strings s and ch as input and assuming ch contains only one
character)
(c) http://www.pythontutor.com/visualize.html#mode
Open file t1.py and copy code below into Python Vizualizer. Make sure you
understand how the program is running and what it is doing as you step through the
execu.on of the program.
11
Recursion: Paper Study
• Open file sum_prod.py
It contains contains 2 func.ons that both compute the
sum: 1+2+3 …+n. One computes it in the ‘usual’ way
using python’s loops (this is called, itera.ve solu.on),
and the other in a recursive way (i.e. using func.on
calls that solve a problem on the smaller problem
instance)
Similarly sum_prod.py contains 2 func.on that both
compute the product 1*2*3…*n (thus they compute
n!, i.e. n factorial) in itera.ve and recursive way (as we
have seen in class)
Study with TAs and understand well all these 4 solu.ons.
12
Recursion: Programming Exercise 1
• Write a recursive func.on (do not use python’s
loops), called m, that computes the following series,
given posi.ve integer i:
• In the “main” write a loop that tests your func.on m
by displaying values m(i) for i = 1, 2, . . . , 10, as follows
m(1)= 0.3333333333333333
m(2)= 0.7333333333333334
m(3)= 1.161904761904762
m(4)= 1.6063492063492064
m(5)= 2.060894660894661
m(6)= 2.5224331224331227
m(7)= 2.9890997890997895
m(8)= 3.459688024393907
m(9)= 3.933372234920223
m(10)= 4.409562711110699
13
Recursion: Programming Exercise 2
• Write a recursive func.on, called count_digits,
that counts the number of digits in a given
posi.ve integer n.
• Test your func.on:
>>> count_digits(0)
1
>>> count_digits(7)
1
>>> count_digits(73)
2
>>> count_digits(13079797)
8
>>>
14
Recursion: Programming Exercise 3
• A string is a palindrome if it reads the same from the le> and from the
right. For example, word “kayak” is a palindrome, so is a name “Anna”, so
is a word “a”. Word “uncle” is not a palindrome.
• Write a recursive func.on, called is_palindrome, that returns True if the
input string is a palindrome and otherwise returns False. Test your
func.on.
• No.ce: a word of length n is a palindrom if 1st and nth lemer are the same,
AND 2nd and (n-1)st are the same, and so on … un.l we get to the “middle”
of the word.
>>> is_palindrome('blurb')
False
>>> is_palindrome('a')
True
>>> is_palindrome('anna')
True
>>> is_palindrome('Anna')
True
>>> is_palindrome("A man, a plan, a canal --
Panama!")
False
>>> is_palindrome("Madam, I'm Adam")
False
15
Checking if a string is a palindrome can be divided into
two subproblems:
1. Check if the 1st and the last character in the string are
the same
2. Ignore the two end characters and check if the rest
of the substring is a palindrome.
No.ce that the 2nd subproblem is the same as the
original problem but smaller in size.
Useful string methods: lower(), and string slicing
Idea/Strategy
16
Recursion: Programming Exercise 4
• Refine your func.on is_palindrome, and call the modified version,
is_palindrome_v2, such that it ignores all characters but the characters
that correspond to the lemers of English alphabet. You may find Python’s
string method .isalpha() useful.
• Test your func.on with the following at least:
>>> is_palindrome_v2("A man, a plan, a canal -- Panama!")
True
>>> is_palindrome_v2("Go hang a salami, I'm a lasagna
hog")
True
>>> is_palindrome_v2("Madam, I'm Adam")
True
>>> is_palindrome_v2("Madam, I'm")
False
>>> is_palindrome_v2('blurb')
False
>>> is_palindrome_v2('a')
True
>>> is_palindrome_v2('Anna')
True
17
Recursion: Programming Exercise 5: GCD
The greatest common divisor (GCD) of two integers (at least one of which is
not zero), is the largest posi.ve integer that divides the numbers without a
remainder. For example, the GCD of 12 and 8 is 4.
The following technique is known as Euclid’s Algorithm because it appears in
Euclid’s Elements (Book 7, ca. 300 BC). It may be the oldest nontrivial algorithm.
The process is based on the observa.on that, if r is the remainder when a is
divided by b, then the common divisors of a and b are the same as the common
divisors of b and r. Thus we can use the equa.on
gcd(a,b) = gcd(b,r)
to successively reduce the problem of compu.ng a GCD to the problem of
compu.ng the GCD of smaller and smaller pairs of integers. For example,
gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4
implies that the GCD of 36 and 20 is 4. It can be shown that for any two star.ng
numbers, this repeated reduc.on eventually produces a pair where the second
number is 0. Then the GCD is the other number in the pair.
Write a recursive func.on called gcd that takes two integer parameters a and
b (you can assume a>=b) and that uses Euclid’s algorithm to compute and return
the greatest common divisor of the two numbers. Test your func.on.
18
Bonus difficult ques.on: GCD
What is the depth of the recursion (i.e. the maximum number of gcd
methods on the stack/memory) of your gcd func.on if you called it
with gcd(36, 20)? You can find this out by drawing the diagrams as
we did in class and or running your func.on and the gcd(36, 20) in
Python Visualizer.
Here is a difficult ques.on and food for thought: What is the
maximum depth of the recursion of your gcd method for general a
and b (where a>=b)?