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

MCS 260 Fall 2021 Worksheet 11 Solutions

  • Course instructor: Emily Dumas
  • Solutions prepared by: Emily Dumas and Jennifer Vaccaro (2020 MCS 260 TA)

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

Solution

In [1]:
"Lazy finite geometric sequence example (with item assignment)"
# MCS 260 Fall 2021 Worksheet 11

class FGS:
    "Lazy finite geometric sequence"
    def __init__(self,start,ratio,length):
        """
        Initialize a finite geometric sequence with first value
        `start`, ratio of successive terms `ratio`, and total
        number of terms `length`.
        """
        self.start = start
        self.ratio = ratio
        self.length = length
    def __len__(self):
        "number of terms"
        return self.length
    def __getitem__(self,idx):
        """
        compute and return the element of the geometric sequence
        at index `idx`
        """
        if idx < 0 or idx >= self.length:
            # The requested index is not valid
            raise IndexError("this FGS has {} terms and so index {} is invalid".format(
                self.length,
                idx
            ))
        return self.start * (self.ratio ** idx)

    def __setitem__(self,idx,val):
        if idx == 0:
            self.start = val
        else:
            raise 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
In [7]:
"Lazy finite geometric sequence example (with item assignment and negative indices)"
# MCS 260 Fall 2021 Worksheet 11

class FGS:
    "Lazy finite geometric sequence"
    def __init__(self,start,ratio,length):
        """
        Initialize a finite geometric sequence with first value
        `start`, ratio of successive terms `ratio`, and total
        number of terms `length`.
        """
        self.start = start
        self.ratio = ratio
        self.length = length
    def __len__(self):
        "number of terms"
        return self.length
    def __getitem__(self,idx):
        """
        compute and return the element of the geometric sequence
        at index `idx`
        """
        # If idx is negative, attempt to convert it to the corresponding positive value
        # adding self.length means that -1 becomes self.length-1, which is the last element
        # similarly, -2 becomes self-length-2, the second-to-last, etc., which is the
        # usual negative index behavior.
        if idx < 0:
            idx += self.length
        
        # Now, if idx is still negative, it means that it was too small (i.e. too negative)
        # for negative indexing to be valid.
        if idx < 0 or idx >= self.length:
            # The requested index is not valid
            raise IndexError("Invalid index requested for FGS with {} terms".format(
                self.length
            ))
        return self.start * (self.ratio ** idx)
    def __setitem__(self,idx,val):
        if idx == 0:
            self.start = val
        else:
            raise IndexError("FGS only supports item assignment at index 0")
In [8]:
G = FGS(2,3,5)
G[-2]
G[-4]
G[-5]
G[-6]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-8-887f13ca8c7f> in <module>
      3 G[-4]
      4 G[-5]
----> 5 G[-6]

<ipython-input-7-5022aed21c89> in __getitem__(self, idx)
     32         if idx < 0 or idx >= self.length:
     33             # The requested index is not valid
---> 34             raise IndexError("Invalid index requested for FGS with {} terms".format(
     35                 self.length
     36             ))

IndexError: Invalid index requested for FGS with 5 terms

Note that the problem didn't specify whether we should also support negative indexing in __setitem__ or not. This solution doesn't, which is sensible when only index 0 can be assigned a new value.

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.)

In [ ]:
def is_palindrome_recursive(s):
    """Determines whether a string is a palindrome recursively"""
    # Base case: all strings of length 0 or 1 are palindromes
    if len(s) == 0:
        return True
    if len(s) == 1:
        return True
    # otherwise, check that the first and last are equal, then
    # recurse on the 'middle' string that's left
    return s[0]==s[-1] and is_palindrome_recursive(s[1:-1])

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
In [11]:
def fib(n):
    """Calculates the nth fibonacci number recursively"""
    # Base case: fib(0)=0 and fib(1)=1
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # If n > 1, recurse on n-1 and n-2
    return fib(n-1) + fib(n-2)

def gib(n):
    """Calculates the nth number in sequence G_n satisfying
    G_0 = G_1 = 1
    G_n = 1 + G_{n-1} + G_{n-2}"""
    if n <= 1:
        return 1
    
    # Otherwise, recurse on n-1 and n-2
    return 1 + gib(n-1) + gib(n-2)
In [15]:
print("fib:")
for n in range(11):
    print(n,fib(n))
    
print("\ngib")
for n in range(11):
    print(n,gib(n))
fib:
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55

gib
0 1
1 1
2 3
3 5
4 9
5 15
6 25
7 41
8 67
9 109
10 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.

Solution

In [16]:
call_record = [] # We'll add a None to this every time fib_record is called

def fib_record(n):
    """Calculates the nth fibonacci number recursively"""
    # Base case: fib(0)=0 and fib(1)=1
    call_record.append(None)
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # If n > 1, recurse on n-1 and n-2
    return fib_record(n-1) + fib_record(n-2)

for n in range(11):
    fib_record(n)
    print("To compute fib({}), total of {} calls to the function were made".format(
        n,
        len(call_record)
    ))
    call_record = []
To compute fib(0), total of 1 calls to the function were made
To compute fib(1), total of 1 calls to the function were made
To compute fib(2), total of 3 calls to the function were made
To compute fib(3), total of 5 calls to the function were made
To compute fib(4), total of 9 calls to the function were made
To compute fib(5), total of 15 calls to the function were made
To compute fib(6), total of 25 calls to the function were made
To compute fib(7), total of 41 calls to the function were made
To compute fib(8), total of 67 calls to the function were made
To compute fib(9), total of 109 calls to the function were made
To compute fib(10), total of 177 calls to the function were made

Comments on the METHOD above: It's possible to add an element to a global list variable from within a function, and have that change persist outside the function. This is because method calls (like listvar.append(...)) don't change a global name to a local one.

In contrast, an approach like this will not work:

call_count = 0

def fib_record(n):
    call_count += 1
    # rest of function here

because the assignment of call_count inside the function creates a new local variable (leaving the global variable of the same name unchanged).

Comments on the NUMBERS above: You might notice this agrees with the sequence $G_n$ that is computed by the function gib(n). However, we only checked 11 terms. With a bit more work, we can verify this for all $n$.

Let's use $CC_n$ to indicate the call count when fib(n) is called, i.e. the total number of fib function calls that occur. We think that $CC_n = G_n$. (We actually renamed fib to fib_record when we added the call count recording feature, but we keep the old name in this paragraph for brevity.)

Step 1: $CC_n = G_n$ for $n=0,1$.

In both of these cases, the function fib returns a value immediately (without calling itself). So we have exactly 1 function call in each case, i.e. $CC_0 = CC_1 = 1$. Similarly, $G_0 = G_1 = 1$ by definition.

Step 2: $CC_n = 1 + CC_{n-1} + CC_{n-2}$ for $n>1$.

When fib is called with a value of n greater than 1, it makes calls to fib(n-1) and fib(n-2). Thus we have the initial call to fib (1) plus all the calls occurring as a result of fib(n-1) and fib(n-2) ($CC_{n-1}$ and $CC_{n-2}$, respectively). The total is $1 + CC_{n-1} + CC_{n-2}$. As this it the number of calls happening as a result of fib(n), this is also equal to $CC_n$. Thus $CC_n = 1 + CC_{n-1} + CC_{n-2}$.

Step 3: Induction.

Both $CC_n$ and $G_n$ are defined by formulas that specify the first two terms, and which specify how to compute a given term using the two before it. It then follows by induction that $CC_n$ and $G_n$ agree for all $n$ (with $n=1$ as the base case and the definitions of $GG_n$ and $CC_n$ providing the inductive step).

The analysis given above is more theoretical and challenging than most we give in MCS 260, and wouldn't be appropriate for homework.

Revision history

  • 2021-11-04 Initial release