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:
(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.)
import fgs
S = fgs.FGS(start=10,ratio=2,length=7)
S[0] # first term
S[1] # second term
# 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:
# 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] = xtranslates 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:
0 should change the start value of the geometric sequence (without changing the ratio or length).IndexErrorExample of what the new behavior should look like:
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
"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"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")
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:
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.)
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:
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 55When you've finished that, make another function gib(n) that generates the sequence $G_n$ defined by this rule:
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 177def 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)
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.
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 herebecause 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.