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

- Course instructor: Emily Dumas

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

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

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

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

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`

.

- 2021-11-01 Initial release