CS 115: Lab 14

Goals

Upon successful completion of this lab, you should be able to trace the execution of simple recursive functions.

Setup and Practice

Setup

If your lab machine was not started in MacOS when you went to use it, reboot it to MacOS.
Follow these procedures to mount your blue home-directory on the local machine and create a PyCharm project (call it Lab14). You will use PyCharm in the next part, but, it is important that you set up your project now so that if you run into any issue, we can resolve them quickly.
Right-click or control-click to download these 2 files and place them into the directory for this lab:
- cities.txt
- cities-small.txt
This lab builds on Lab 10, in which you built, sorted and searched a list of cities. Copy your Lab 10 code, specifically lab10c.py, into the Lab14 directory and rename it to lab14b.py.

Part A: Recursion practice

Before you start writing your own code, you'll use the the online Python 3 tutor to trace the execution of recursive functions. Try to predict what will happen before stepping through the code in the tutor.

This part is important to understand how recursion works --- there is usually a similar question in Exam 3!!

Instructions

Enter the following code into the tutor:

def f(x):
    if x <= 1: return 1
    temp = f(x - 1)
    return x * temp


def main():
    a = f(4) # Statement 1


main()

Trace through the execution of Statement 1, and answer Question 1 in the writeup.

Enter the following code into the tutor:

def reverse(s):
    if len(s) <= 1: return s
    return s[-1] + reverse(s[0:-1])


def main():
    a = reverse('H') # Statement 1
    b = reverse('seawolf') # Statement 2


main()

Trace through the execution of Statement 2, and answer Question 2 in the writeup.

Enter the following code into the tutor:

def mystery(x):
    if x == 0: return 0
    return (x % 10) + mystery(x // 10)


def main():
    a = mystery(46213)


main()

Trace through the execution of the function calls, and answer Questions 3 and 4 in your writeup.

Enter the following code into the tutor:

def mystery2(L, i):
    if len(L) <= i: return 0
    return L[i] + mystery2(L, i + 1)


def mystery1(L):
    return mystery2(L, 0)


def main():
    a = mystery1([4, 10, 1, 3])


main()

Trace through the execution of the function calls, and answer Questions 5 and 6 in your writeup.
Continue to Part B.

Part B: Recursive binary search

This part builds on Lab 10, in which you built, sorted, and searched a list of cities. We will be refactoring your binary search logic, to implement a recursive version of that logic.

Instructions

Open lab14b.py (created during Setup) and, in main(), comment out the code where you call and print the result of linear search. Modify your print statements until they match this sample output:

Name of input file: cities-small.txt

The original list of cities is:
0: Santa Rosa
1: Petaluma
2: Rohnert Park
3: Windsor
4: Healdsburg

After sorting, the new list is:
0: Healdsburg
1: Petaluma
2: Rohnert Park
3: Santa Rosa
4: Windsor

Enter the name of a city: Petaluma
**Binary search iterations: 3
The position of Petaluma is: 1

Enter the name of a city: quit

Go into the function definition for binary_search(). Right after you have calculated the initial values of first and last, add the following line of code:
```
return binary_search_recursive(search_list, value_to_find, first, last)
```
This will call a new, recursive binary search function that you are about to write, and return its result.

Because this is a return statement, you won't end up executing anything in the function below this line. However, you should keep this code around for your reference.
Write a def line for this new binary_search_recursive function. Then, write a docstring for the function. The parameters of this function are:
- The list to search (which must already be sorted)
- The value to search for
- The first index to inspect during the search
- The last index to inspect during the search
If the value to search for is in the list, this function will eventually return its index. Otherwise, this function will return None.

Inside your new function, add a line of code that prints first and last. Here is an example of what your program should do so far:

Name of input file: cities-small.txt

The original list of cities is:
0: Santa Rosa
1: Petaluma
2: Rohnert Park
3: Windsor
4: Healdsburg

After sorting, the new list is:
0: Healdsburg
1: Petaluma
2: Rohnert Park
3: Santa Rosa
4: Windsor

Enter the name of a city: Petaluma
Binary searching between 0 and 4
The position of Petaluma is: None

Enter the name of a city: quit

Below the print statement, add a line of code that calculates the index of the middle element of the list. You can reuse the formula from the loop in your original binary search function.

Add code that checks to see if the middle element of the list is the value that you're looking for. If it is, then you should return the index of the middle element.

Sample input and output so far:

Name of input file: cities-small.txt

The original list of cities is:
0: Santa Rosa
1: Petaluma
2: Rohnert Park
3: Windsor
4: Healdsburg

After sorting, the new list is:
0: Healdsburg
1: Petaluma
2: Rohnert Park
3: Santa Rosa
4: Windsor

Enter the name of a city: Rohnert Park
Binary searching between 0 and 4
The position of Rohnert Park is: 2

Enter the name of a city: Healdsburg
Binary searching between 0 and 4
The position of Healdsburg is: None

Enter the name of a city: quit

Copy (or rewrite) your code that adjusts first or last, based on whether the value you are looking for comes before or after the middle element.
Rather than using a loop, you are going to have this function call itself (which is essential to recursion), using your new values of first and last. At the very end of your function, include a return statement:
```
return _______________________
```
Fill in the blank with a call to binary_search_recursive that passes it the original list, the value to look for, and the new values of first and last.
Answer Question 7 in your writeup.

Finally, add a line to the beginning of your new function (just after the print statement) that will return None (or just return) if the values of first and last are unreasonable (that is, if first is actually after last). Sample output:

Name of input file: cities-small.txt

The original list of cities is:
0: Santa Rosa
1: Petaluma
2: Rohnert Park
3: Windsor
4: Healdsburg

After sorting, the new list is:
0: Healdsburg
1: Petaluma
2: Rohnert Park
3: Santa Rosa
4: Windsor

Enter the name of a city: San Francisco
Binary searching between 0 and 4
Binary searching between 3 and 4
Binary searching between 3 and 2
The position of San Francisco is: None

Enter the name of a city: quit

Answer Question 8 in your writeup.
Demo. When your code is correct, call an instructor to demo.
Make sure your program and functions have docstrings and that they all are up-to-date with your code.
Continue to the next part to submit your program.

Assignment Submission

Instructions

Answer the last question (#9) in your Moodle writeup. Review your answers, and then click the "Next" button at the bottom of the quiz. Once you do that, you should see a "Summary of Attempt" screen.
Click the "Submit all and finish" button. Warning: You must hit "Submit all and finish" so that your writeup can be graded! It is not submitted until you do this. Once you have submitted your quiz, you should see something similar to this at the top of your Moodle window. The important part is that the State shows up as Finished.

Please leave this tab open in your browser.
Click on the "Lab 14 code" link in Moodle and open in a new tab. Follow the instructions to upload your source code (lab14b.py) for Lab14. You could either browse for your code or, using a finder window, drag and drop your lab14b.py from your cs115/Lab14 folder to Moodle. You should subsequently see a dialog box which indicates 'Submission Status' as 'Submitted for grading'. Leave this tab open in your browser.
With these confirmation pages open in your browser, you may call an instructor over to verify that you have completed every part of the lab. Otherwise, you are done!