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
first_item = 28, lower_list = , higher_list = 
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 = , 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: