Make sure all programs are saved to your cs21/labs/10 directory. Files outside this directory will not be graded.
$ update21
$ cd ~/cs21/labs/10In a file called recursion_practice.py, implement recursive functions to accomplish each of the following tasks:
fibonacci(0) should return 0, fibonacci(1) should return 1, and all other Fibonacci numbers can be calculated as the sum of the two previous Fibonacci numbers, e.g. 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, and so on. You can assume the function will only be called with non-negative integers.reverseString("hello") should return "olleh".isSorted([-4, 2, 13]) should return True, while isSorted([3, 0, 2]) should return False.countOccurrences([1, 4, 3, 1, 1, 3], 1) should return 3 while countOccurrences([1, 4, 3, 1, 1, 3], 16) should return 0.Write a main() function that tests each of these recursive functions. You can use the examples above, but write at least three additional tests of your own for each function. Try to test the functions in different situations, including the corner cases, like when an int parameter is 0, a string parameter is "", or a list parameter is [].
Use a combination of prints and asserts to write your tests. The following code:
assert(reverseString("hello") == "olleh")would produce no output if the expression inside the assert evaluates to True, but would print an error message if it evaluates to False.
Your recursive functions may not make use of any loops—that would be defeating the purpose.
When you solve a problem recursively, you may want to start by identifying the base case (or base cases). These are versions of the problem that can be solved right away, without a recursive call. Next, comes the "leap of faith." Assume that, by some miracle, you will be able to complete the recursive function. How could you use it on a smaller version of the problem to solve the original problem?
If you're struggling to get started, try defining an iterative version of the function first (i.e. one that does use loops). If your iterative version makes use of an accumulator, you may wish to add an additional parameter to the recursive function that acts like an accumulator. If the task was to sum the integers in a list, we could define this function (1) iteratively using an accumulator variable:
def sumList(L):
accum = 0
for i in range(len(L)):
accum += L[i]
return accumor (2) recursively using an accumulator parameter:
def sumList(L, accum):
if len(L) == 0:
return accum
else:
return sumList(L[1:], L[0] + accum)or (3) recursively without an explicit accumulator parameter:
def sumList(L):
if len(L) == 0:
return 0
else:
return L[0] + sumList(L[1:])When using option 2, we would call sumList with a second argument of 0.
This semester many of you have experienced the unfortunate situation in which python confidently reports a syntax error on a particular line, when really you are missing a parenthesis on the previous line.
# This line is missing a closing parenthesis
x = int(input("Enter your favorite number: ")
# But python tells you the syntax error is on this line
print("%d is my favorite number too." % x)This happens because python thinks that the expression is continuing onto subsequent lines, but we have rarely, if ever, written expressions that extend over multiple lines. Let's fix this issue and improve the well-being of future CS 21 students, and let's do it using recursion!
Write a program, check_parens.py, that gets the name of a python file from its user, goes through the file line by line, and determines whether there are any lines that contain unbalanced parentheses.
$ python3 check_parens.py
Enter file name: no_issues.py
File no_issues.py has no unbalanced parentheses
$ python3 check_parens.py
Enter file name: has_issues.py
Unbalanced parentheses on line 2 of has_issues.py
x = int(input("Enter a number: ")
Unbalanced parentheses on line 3 of has_issues.py
y = int input("Enter another number: "))
Unbalanced parentheses on line 4 of has_issues.py
z = (x + 2) * )y - 3(
Your program should define and make use of a function, isBalanced, that takes in a line from the file as a string and returns a boolean indicating whether that line has balanced parentheses. A return value of True means the line is balanced, False means it is not.
isBalanced will delegate most of the work to a recursive function called isBalancedHelper. isBalancedHelper should recursively examine the characters in the string from left to right, while keeping track of how many open parentheses have not yet been closed. When you encounter a "(" this increases the unclosed parentheses count by 1. A ")" decreases the count by 1. If the unclosed parentheses count ever becomes negative, you have unbalanced parentheses. At the end of the string, the count should be 0. Keep track of the count in a parameter.
isBalanced is just a wrapper around isBalancedHelper that ensures the initial unclosed parentheses count is 0.
def isBalancedHelper(s, unclosedParens):
# Your recursive code here
def isBalanced(s):
return isBalancedHelper(s, 0)You may wish to test isBalanced in isolation, apart from the code that reads in the input file.
isBalanced("((1 + 2) * (3 + 4))\n") # should return True
isBalanced("(1 + 2) * (3 + 4))\n") # should return False
isBalanced("# line without parens\n") # should return TrueOne limitation of this program is that it can make mistakes on lines containing parentheses inside strings or comments. If you run check_parens.py on itself, you will likely encounter this limitation.
isBalanced("print('(')\n") # returns False (mistakenly)Once you are satisfied with your programs, fill out the questionnaire in QUESTIONS-10.txt. Then run handin21 a final time to make sure we have access to the most recent versions of your file.