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

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

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

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

- Sample programs
- Especially fgs.py and factorial.py

- Lecture 27 - OOP 3 (inheritance)
- Lecture 28 - OOP 4 (protocols)
- Lecture 29 - Recursion
- Downey's book

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

In [2]:

```
import fgs
S = fgs.FGS(start=10,ratio=2,length=7)
S[0] # first term
```

Out[2]:

In [3]:

```
S[1] # second term
```

Out[3]:

In [4]:

```
# all the terms
for term in S:
print(term)
```

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
```

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
```

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")
```

`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]
```

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.

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])
```

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

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`

.

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 = []
```

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

- 2021-11-04 Initial release