A document from MCS 260 Fall 2021, instructor David Dumas. You can also get the notebook file.

MCS 260 Fall 2021 Worksheet 11

  • Course instructor: David Dumas

Topics

This worksheet focuses on recursion and the additional aspects of object-oriented programming that were covered last week.

Resources

The main course materials to refer to for this worksheet are:

(Lecture videos are not linked on worksheets, but are also useful to review while working on worksheets. Video links can be found in the course course Blackboard site.)

1. Item assignment and FGS

In Lecture 28 we built a custom sequence class FGS in fgs.py. Recall that objects of this class represent finite geometric sequences, as specified by a start value, ratio, and length.

Here's a quick reminder about how you can work with objects of this class:

In [2]:
import fgs

S = fgs.FGS(start=10,ratio=2,length=7)
S[0] # first term
Out[2]:
10
In [3]:
S[1] # second term
Out[3]:
20
In [4]:
# all the terms
for term in S:
    print(term)

10
20
40
80
160
320
640

At the moment, you can't use item assignment with class FGS, e.g. the command below would raise an exception:

In [5]:
# This will cause an error because we haven't defined item assignment for class FGS.
S[2] = 5

Add item assignment to class FGS

Item assignment in Python is handled by a special method __setitem__. The statement

obj[5] = x

translates into the method call

obj.__setitem__(5,x)

i.e. the first argument to __setitem__ is the index, and the second is the value being assigned at that index.

For FGS, please make item assignment work this way:

  • Assigning a different value to the item at index 0 should change the start value of the geometric sequence (without changing the ratio or length).
  • An attempt to assign to any other index should raise an IndexError

Example of what the new behavior should look like:

In [8]:
import fgs

T = fgs.FGS(start=1,ratio=3,length=5)
print("The start is {} right now.  Items:".format(T.start))
for x in T:
    print(x)

# change start value to 5
T[0] = 5

print("The start is {} right now.  Items:".format(T.start))
for x in T:
    print(x)

# change start value to 0.1
T[0] = 0.1


print("The start is {} right now.  Items:".format(T.start))
for x in T:
    print(x)

print("The next line should produce an exception.")
T[1] = 30

The start is 1 right now.  Items:
1
3
9
27
81
The start is 5 right now.  Items:
5
15
45
135
405
The start is 0.1 right now.  Items:
0.1
0.30000000000000004
0.9
2.7
8.1
The next line should produce an exception.

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-8-f38dc9d1b10c> in <module>
     22 
     23 print("The next line should produce an exception.")
---> 24 T[1] = 30

~/teaching/mcs260/public/samplecode/oop/fgs.py in __setitem__(self, idx, val)
     35             self.start = val
     36         else:
---> 37             raise IndexError("FGS only supports item assignment at index 0")

IndexError: FGS only supports item assignment at index 0

2. Negative index support in FGS

However, the FGS class we wrote in lecture 28 doesn't allow indexing with negative numbers, e.g. where [-1] means the last element, etc..

Modify FiniteGeometricSeries so that it does support negative indices in the same way that list does. However, negative indices that are too large in magnitude to represent an item in the series should still raise an exception.

Below is a transcript of a test of the updated module in the REPL. Your class should behave in the same way after the modifications.

>>> import fgs
>>> S = fgs.FGS(start=2,ratio=3,length=5)
>>> S[4]
162
>>> S[-1]
162
>>> S[-2]
54
>>> S[-500]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/ddumas/Dropbox/teaching/mcs260/samplecode/gs/gs_practice.py", line 23, in __getitem__
    raise IndexError("index out of range for series with {} terms".format(
IndexError: index out of range for series with 5 terms

3. Recursive palindrome detector

Recall that a palindrome is a word (or string) that is unchanged after it is reversed. For example, "racecar" or "noon", and "radar" are all palindromes.

Here is a description of a palindrome that suggests a recursive way of checking whether a string is a palindrome or not:

  • Any string with 0 or 1 characters is a palindrome
  • A string with at least 2 characters is a palindrome if both of these conditions are met:
    • The first and last characters are equal
    • After the first and last characters are removed, what remains is a palindrome

Use this description to write a function is_palindrome_recursive(s) that returns True if string s is a palindrome, and False otherwise.

(Note: It's not hard to use built-in features of Python to check for palindromes, but this problem is specifically testing whether you can do it recursively using the strategy outlined above.)

4. Fibonacci numbers and a variation thereof

The Fibonacci numbers are the sequence of positive integers $F_i$ defined as follows:

  • $F_0 = 0$ and $F_1 = 1$
  • For $i > 1$ we have $F_i = F_{i-1} + F_{i-2}$.

Since this definition of $F_i$ involves other Fibonacci numbers, it naturally lends itself to recursion. Write a function fib(n) that calculates $F_n$ using recursion.

Test your function to ensure that it produces the following list:

n      0  1  2  3  4  5  6  7   8   9   10
fib(n) 0  1  1  2  3  5  8  13  21  34  55

When you've finished that, make another function gib(n) that generates the sequence $G_n$ defined by this rule:

  • $G_0 = 1$ and $G_1 = 1$
  • For $i>1$ we have $G_i = 1 + G_{i-1} + G_{i-2}$

Test it and make sure it produces the following list:

n      0  1  2  3  4  5  6  7   8   9   10
gib(n) 1  1  3  5  9 15 25 41  67 109  177

5. Challenge: Fibonacci call count

This problem builds on the previous one, and is a bit more challenging.

When you call fib(n), how many times does the fib function get called in total? It calls itself, so you should expect the answer will often be greater than $1$.

To start exploring this, you might first add a print() statement in the body of fib(n) so that you can see how many calls are made. After trying this out a few times, can you see a pattern? Can you analyze it theoretically?

To collect data systematically, you might want to instead have a way to get the count of calls automatically. Here's one way to do that: Outside the function, make a list L that is initially empty. Inside the function fib, make the first line append a value to L. Then, after calling fib, the length of L is the number of calls to fib. Of course, you'll need to reset the list L to be empty before calling fib again if you want to count the number of calls for another starting value of n.

The final answer to the question (how many calls are made, as a function of n) should be a formula involving n.

Revision history

  • 2021-11-01 Initial release