CODEWITHSUNDEEP
pythonrecursion
user2083363
user2083363

Reputation: 51

Recursion in Python

The problem is about writing a recursive function, "def EhMensuravel (target, weight)" that determines whether it is possible to measure the value desired target with a given set of weights on a twin-pan balance. The weights available are stored in the list "weights". Remebering that the weights can be placed on the plate opposite that is occupied by the target weight, on the same plate of the target weight or be not used.

The code I made is that, but something is wrong.

weights = [1, 2, 3]
matrix = []

def createaMatrix():
    for i in range(len(weights)):
        matrix.append([])
    for j in range(3):
        for i in range(len(weights)):
            if j==0:
                matrix[j].append(weights[i])
            if j==1:
                matrix[j].append(-weights[i])
            if j==2:
                matrix[j].append(0)

createMatrix()


def EhMensuravel(entry, weights, final_weight=0):
    if final_weight == entry:
        return True
    for j in range(3):
        for i in range(len(weight)):
            final_weight += matrix[i][j]
            return EhMensuravel(entry, weight[1:], final_weight)

EDIT: For example, When I try print EhMensuravel(4, weights), the output is:

>>> 
1
2
3
None
>>>

Upvotes: 0

Views: 3827

Answers (1)

wasserfeder
wasserfeder

Reputation: 486

You can make the recursion very simple even without the global matrix like this

weights = [1, 2, 3]

def EhMensuravel(entry, weights, weight_idx = 0):
    if entry == 0:
        return True

    if weight_idx == len(weights):
        return False

    if EhMensuravel(entry + weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry - weights[weight_idx], weights, weight_idx+1):
        return True

    if EhMensuravel(entry, weights, weight_idx+1):
        return True

    return False

print EhMensuravel(4, weights)

The first if statement just says that 0 is measurable. The second if just assures that there are still weights left. The next 3 recursive calls just update the current weight entry by adding, subtracting or ignoring the current weight and restart the search from the next weight. If no solution was found, then False is returned.

Upvotes: 1

Related Questions