Assignment 4: Recursion and Complexity

Instructions

Part 1 - Recursion

Write recursive functions that solve each of the following problems. Your functions must be recursive -- that is, they should have a base case and, in each recursive call, your problem should be reduced to an identical problem of a smaller size. You should have no loops in your code. Your solutions should not be using built-in functions with the exception of len(), str(), append(), extend() and int(), isinstance(), .count(). Solutions that are not recursive will not be assigned a passing grade.

1. Write a function calledfindPairswhich takes a non-negative integer as its parameter and returns the number ofpairsof numbers within the integer that sum to 10. Note that a digit can be used as part of more than one pairing. For example,findPairs(7645238)would return 3. Here's a breakdown of how that value was obtained:

7 + 3 = 10 (first and second last digits add to 10).

6 + 4 = 10 (second and third digits add to 10).

2 + 8 = 10(fifth and last digits add to 10).

2. In this question, you will writetwofunctions. Ensure that your recursive functions involving lists work for all possible cases (i.e. empty lists).

Write arecursivefunction calledrecMinthat accepts a list of lists callednestedLisas its parameter and returns the smallest value innestedLis.If the list is empty, return None.

For example, if your function was called with the following nested list: [66, [73,89,42,32], 62, [24, 32], 99 ], the value 24 would be returned as it is the smallest value in the nested list.

Write arecursivefunction calledmergeListthat accepts a list of lists callednestedLisas its parameter and returns a single list containing all of the values innestedLis.If the list is empty, return the empty list.

For example, if your function was called with the following nested list: [66, [73,89,42,32], 62, [24, 32], 99 ], the following list would be returned: [66,73,89,42,32,62,24,32,99].

3. Write a recursive function calledaddNextwhich takes a single integernas its parameter and calculates the sum of everyotherinteger between 0 andn.For example, if youraddNextfunction was called with the integer 6,addNextwould return 12. This value was calculated by adding together 6+4+2+0.

4. Write a recursive function calledswapElements. This function accepts a list of integers as its parameter and returns a copy of the list in which neighboring elements have been swapped. For example, callingswapElementswith the list [3,8,2,1] would return a copy of the list with consecutive elements swapped: [8,3,1,2]. If the length of the list is odd, your function doesn't need to swap the last element - this element can remain in its original position. If the list is empty, return an empty list.

5. Write a recursive function calledfunkyNumsthat accepts a positive integer as its parameter and writes the provided integer to the console backwards. For example, callingfunkyNumswith the integer 5637 would print 7365 to the console.

6. You work at the local post office and have an infinite supply of postage stamps of a variety of denominations. Write a recursive function calledcalcStampthat returns the minimum number of stamps that would be required in order to pay the postage cost. The function should accept a postage cost and a list of integers representing the stamp denominations as its parameters. The list of denominations can be of any length.

Example:calcStamp(11, [1, 2, 5, 12, 14, 18]) would return3 since the minimum number of stamps needed to make 11 based on the available denominations would be 3. A possible stamp combination using only 3 stamps would be [5,5,1].

Part 2 - Testing Your Recursive Functions

Please include a testing script demonstrating the functionality of each of your recursive functions. Your testing script should include tests for both regular and special cases. For recursive functions involving lists, a special case would be a situation where the list that is passed in to the function is the empty list. Your functions should work properly in these special cases.

Part 3 - Computational Complexity

7. I have included this question to provide you with practice at identifying the complexity of algorithms. Please identify the complexity of the following algorithm. You must also provide ajustificationthat explains how you arrived at your answer. Even if your answer is incorrect, a justification will allow us to give you part marks, as well as feedback prior to the exam.

def mystery(lis): n = len(lis) for index in range(n): x = 2*index % n lis[index],lis[x] = lis[x],lis[index] print(lis) Bottom of Form