Python代写: 实践Recursion, Quicksort

使用Python实践recursion, 快排算法等。

Use recursion to solve the problems as indicated.

Question 1: Write a recursive program that calculates triangle numbers (do not use any loops in this program).

A triangle number of a positive integer is the sum of all the numbers less than or equal to that number. For example, triangle(5) = 1 + 2 + 3 +4 + 5 = 15; triangle(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, etc.

Question 2: Write a recursive program that requests an answer to the question “Are we there yet?” using an input statement and terminates if the user answers ‘yes’, but executes a recursive call if the user answers anything else (do not use any loops in this program).

Question 3: Write a recursive function that sorts a list of numbers using the following strategy (this is an implementation of the Quicksort algorithm):

If the list contains one item, return that list (it is sorted).

Else If the list contains 2 items, compare the two items with < and return a list with the smaller item first.

Else (this is the recursive step):

Choose the first item in the list (the pivot) and create two smaller lists: one list of all the items larger than the first item and one list of all items smaller than that item


Create a new list by adding the pivot to the end of the lower list (append) and then adding the higher list to the end as well (extend)

Trace of Example: input_list = [35, 42, 39, 7, 49, 46, 33, 43, 28, 25]

first function call: first item = 35, lower_list = [7,28,25,33], higher_list = [42, 39, 49, 46, 43]

call function lower_list

first_item = 7, lower_list = [], higher_list = [28,25,33]

lower_list is empty, so ignore it

higher_list

first_item = 28, lower_list = [25], higher_list = [33]

combine lower_list, first_item, higher_list –> return[25,28,33]

combine 7 with higher_list (ignoring empty lower list) –> [7,28,25,33]

call function with higher_list

first_item = 42, lower_list = [39], higher_list = [49, 46, 43]

higher_list – first_item = 49, lower_list = [46, 43], higher_list = []


combine lists and first item, return [39,42,43,46,49]

combine lists and first item, return [7,28,25,33,35,39,42,43,46,49]

Question 4 (Extra Extra Credit): Write a program using the turtle module. The turtle will draw a spiral recursively using a function called: turtle_spiral with one parameter: length.

The base case is when the length is equal to 1. In this case, the turtle will simply put the pen down.

For all other lengths, the turtle should:

To make the results more visible, alternate pencolors, e.g., between black and yellow, but only change pen colors on every 4rth line (e.g., using modulus),

For example, the command: turtle_spiral(200) would result in an image something like the following:

kamisama wechat
KamiSama