Python代写：CS112-ProgrammingAssignment11

CS 112 – Programming Assignment 11

Recursion

Assignment basics file:

1	https://piazza.com/class_profile/get_resource/k4wblafqtoj2cx/k5x3ennufm34cg

Tester file:

1	will be available in a few days

Background

The purpose of this assignment is to practice recursive functions in Python.

Guidelines

 Loops are banned. You may not use a for loop or a while loop anywhere in your solution.
 You must use recursion in each function in order to receive full credit.
 You are not allowed to import anything.
 You are not allowed to use anything that hasn’t been covered in class, including but not
limited to: list comprehension, lambda functions, generators, builtins like zip(), etc.
 From the built-in functionswe have covered in class, you are not allowed to call max().
Everything else is fair game.
 You are allowed to use sets, dictionaries, and any of their respective operations.
 You are allowed to use any string method except for string.join()
 You can do string slicing, but you cannot use the string[::-1] shortcut.
 You can use any list operation, except for list.sort() and list.reverse()
 Do not hard code to the examples or to the tester.
 You should be skimming Piazza regularly in the event that clarifications to this assignment
get made. Turn on your email digests!

Testing

In this assignment testing will be done as before. You will start working on the assignment

without a tester, and you will do your own testing based on the examples we provide in this

document as well as other examples you can come up with based on the provided files. A few

days later we will provide an actual tester but don’t wait for it in order to start working on the

assignment as there won’t be enough time to complete it before the deadline. The purpose of

the delayed release of the tester is for you to put more emphasis/effort on writing logically

correct programs instead of trying to pass certain tests only. When we post the tester, we’re

going to omit some of the test cases that will be used for grading. This means that there might

be errors in your code even if the tester is giving you no errors. You must do your own checks to

make sure that you haven’t missed anything and your code is correct. Youdo not need to modify

the tester, just test on your own any way you like. Again, the goal is to help you put more focus

on writing logically correct programs instead of trying to pass certain tests only.

Grading Rubric

Submitted correctly:
Code is well commented:
Tester calculations correct:
Unknown test cases
TOTAL:
+EC

2

8

60

30

100 +

# see assignment basics file for file requirements!
# see assignment basics file for how to comment!
# see assignment basics file for how to test!
# test cases that are omitted from the tester

Note : If your code does not run and crashes due to errors, it will receive zero points. Turning in
running code is essential.

Assumptions

You may assume that:

The types of the values that are sent to the functions are the proper ones, you don’t have
to validate them (e.g. filename will be a string, not an integer, etc.).
The lists passed to merge() will be in ascending order.

Functions

No fancy narrative this time, just a few problems to solve using recursion. You must use
recursion in each function to get full credit. The use of a loop in one of these functions will
result in a zero for that function. You may not alter the function signatures.

def my_join(strings, char):
Description: Recreate the built in .join() function using recursion.

1	Parameters: strings , a list of strings; char , a single character

1	Return value: a string, the result of joining each string in the list with given character inbetween

Examples:

1
2
3

my_join(['a'], '*') → 'a'
my_join(['a','b'], '*') → 'a*b'
my_join(['x','y','z'], '$') → 'x$y$z'

def skip_sum(nums, n):
Description: find the sum of every nth number in the given list

1	Parameters: nums , a list of integers; n , a nonzero positive integer

1	Return value: an integer, the sum of every nth number

Examples:

1 2	skip_sum([1,2,3,4,5,6], 2) → 9 # 1 + 3 + 5 skip_sum([1,2,3,4,5,6], 3) → 5 # 1 + 4

def is_palindrome(word):
Description: A palindrome is a word that can be written forwards the same as it can be written
backwards. Determine if the given string is a palindrome or not.

1	Parameters: word, the string that we are checking

1	Return value: a boolean, True if the word is a palindrome, and False otherwise.

Examples:

1 2	is_palindrome('tacocat') → True is_palindrome('watermelon') → False

def merge(listA, listB):
Description: Combine two lists into one list, maintaining the order of the elements. You should
assume that both lists given to this function contain elements in ascending order (smallest first).

1	Parameters: listA, listB, two lists of elements (could be anything – assume homogenous data)

1	Return value: a list, the combination of elements from listA and listB in ascending order.

Examples:

1
2
3

merge([1,2,3], [4,5,6]) → [1,2,3,4,5,6]
merge([1,2,3], [2,3,4]) → [1,2,2,3,3,4]
merge([2,4,6], [1,3,5]) → [1,2,3,4,5,6]

Extra Credit (10 points)

def largest_sum(xs, x, y):
Description: Zig-zag through a two dimensional list of integers from some starting point until you
reach one of the list’s boundaries, computing the largest sum that you find along the way. X and Y
represent the row and column position in xs of the first number to use in the sum. The zig-zag
patten is made by limiting yourself to only looking at the number immediately on the right of (x,y)
and the number immediately below (x,y) when figuring out which of those numbers yields the
largest sum.

1	Parameters: xs, a 2D list of integers, x,y are the row and col position in xs

1	Return value: an integer, the largest sum you can find from position (x,y)

Examples:

largest_sum([[1,2],[3,0]],0,0) → 4
largest_sum([[5,6,1],[2,3,3]],0,0) → 17
largest_sum([[0,7,5],[6,-1,4],[-5,5,2]],0,0) → 18
largest_sum([[0,7,5],[6,-1,4],[-5,5,2]],1,1) → 6