lab08 : Recursive functions

num ready? description assigned due
lab08 true Recursive functions Tue 11/28 08:00AM Sat 12/02 05:00PM

Learning Goals

This lab may be done individually or in pairs

Getting started

Note: All your solutions must use RECURSION

Multiply without the * operator

In lab08.py file create a stub for the function recProduct that takes two integer arguments a and b and returns the product of the two numbers. Your task is to implement this function without using the * (multiply) operator, only + (addition) and RECURSION instead of loops. Your program should work for positive, and negative values of a and b.

Before implementing the function, work on developing an algorithm. For starters, consider the case where b takes only non-negative values and a may be positive, negative or zero. Recognize that:

a * b = a + a + a + ... + a (with b copies of a added together)

E.g.,

3 * 4 = 3 + 3 + 3 + 3

The above describes a form of the solution that does not use the multiply operator just the ‘+’ operator. The next step is to write the recursive form of your solution.

Just for practice, take a minute to (a) determine the base case and (b) write the recursive step without looking below. After you’ve got it, read on. If you don’t know where to ask, please ask for help. Scroll down when you have an answer.

Your base case probably looks something like:

a * 0 = 0

That is, when b is 0, then the product of 0 times any number is 0.

Your recursive step should be something like:

a * b = a + a * (b-1)

In a recursive implementation, you must have (1) a base case (2) a recursive case where the * operator in the expression a + a * (b-1) is replaced by a call to the very function you are implementing: recProduct

Now, implement your recProduct() function. Once you have that, its time to test you code. Using the pytest framework, test your code for some typical inputs. Add your test code to lab08_student_tests.py

For example check that your program does the following:

recProduct(0,5) returns 0

recProduct(1,5) returns 5

recProduct(-1,5) returns -5

A Useful tip from lab06

As you know, this Unix shell command runs the tests in lab08_student_tests.py

python3 -m pytest lab08_student_tests.py

If you have LOTS of tests in your file, and you ONLY want to run some of them, you can use -k string to run ONLY the tests that contain a certain string. For example, suppose you want to focus ONLY on the tests for recProduct. You can run:

python3 -m pytest lab08_student_tests.py -k recProduct

Change recProduct to any function that you want, and only the tests that contain that string will be run. The others will be “de-selected”.

Once you have tested your code for the cases where the parameter b is non-negative, while a is any integer (positive, negative or zero), try to write a few additional test cases where the parameters b is negative. Here are a few example cases:

recProduct(5,-1) should return -5

recProduct(-5,-1) should return 5

Implement the logic needed to handle the case where b is negative in order to pass the additional test cases.

Check if a string is a palindrome

In lab08.py file create a stub for the function isPalindrome that takes one string as argument and returns True if the string is a palindrome and False otherwise. You should also return True if the string is empty. Assume that your input is just a single word with no spaces. Your solution MUST use recursion.

A palindrome is a sequence of characters which reads the same backward as forward, such as ‘madam’, ‘racecar’ or ‘detartrated’. You must ignore the case of the characters when comparing them, so your function should return True for the word ‘raCecaR’

Add test cases to test isPalindrome() in lab08_student_tests.py. Then implement your function. Just like the previous problem, remember that you need to first write the base case that returns the correct value for the smallest possible input, which may be an empty string or a string with just one letter. This is known as the ‘base case’. You then need to write the recursive case. The recursive case describes your problem in terms of itself (but on a smaller input size). In this case, your function not only calls itself but also makes progress towards the base case.

Submission

Great job working through lab08!

The page for submitting lab08 is here: https://submit.cs.ucsb.edu/form/project/904/submission

Upload your lab08.py and lab08_student_tests.py file.

Submission from CSIL command line

If you are working on the ECI/CSIL/lab linux systems, you can also submit at the command line with this command:

~submit/submit -p 904 ~/cs8/lab08/lab08.py lab08_student_tests.py

Notes on using the command line version of submit:

Adapted from SPIS-2016 (UCSD)