CODEWITHSUNDEEP
pythonalgorithmrecursion
Jonathan Rukaj
Jonathan Rukaj

Reputation: 21

Recursive algorithm that displays if it is possible to choose two integers from a list of integers such that their difference equals a given value

Full question: Design a recursive algorithm that will display whether it is possible to choose two integers from a list of integers such that the difference of the two equals a given value. Hint: You may wish to invoke another algorithm, (i.e., function), that accepts more parameters which performs the recursion. Submit a python function is_diff_two(values,diff) that take a list and the desired difference as a non-negative integer and returns true or false. The only functions you may use are: print, str, int, float, bool, len, list, range, abs, round, pow. We will not deduct for the use of str(), but you do not actually need it. Do not import libraries.

Keywords allowed: if, elif, else, and, or, not, return, def, assert,

Keywords not allowed: for, while, in, import.

Note that you may not use slicing(AKA colons in your indicies).

I am having trouble implementing this algorithm; I'm not sure what the base case is, how to use a helper method, or how to do the problem without using loops or python list slicing. What I currently have is a helper method called check_diff(), that takes a list as a parameter, recursively iterating through the list and appending to a new list all the possible differences between values in the original list. I was then going to call the method in the is_diff_two() method, in one line checking to see if the diff parameter is in the list - if so, it should return true, if not then false. This is what I have for my helper method thus far, but I cannot figure out how to correctly recurse through the list and get all the possible differences.

def check_diff(values):
    diff_list = []
    if len(values) == 1:
        return diff_list
    else:
        diff_list.append(values[0] - check_diff(values[1]))
        return values[0] - check_diff(values[1])

Upvotes: 2

Views: 1939

Answers (1)

blhsing
blhsing

Reputation: 106513

You can make a function that optionally takes two indices of the given list, and makes recursive calls with the second indice incremented until it is out of range, at which point make recursive calls with first indice incremented until it is out of range, at which point return False if there is no two values at the two indices found to differ by the target value, or return True if any such values are found:

def is_diff_two(values, diff, a=0, b=1):
    if a == len(values):
        return False
    if b == len(values):
        return is_diff_two(values, diff, a + 1, a + 2)
    return abs(values[a] - values[b]) == diff or is_diff_two(values, diff, a, b + 1)

so that is_diff_two([2, 4, 8], 3) returns False, and that is_diff_two([2, 4, 8], 4) returns True.

Upvotes: 2

Related Questions