Recursion in Python

Question

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
>>>

"Something is wrong." Please edit your question to say what is wrong. — Francis Avila
– Francis Avila, Commented Feb 18, 2013 at 22:56
Please share the output of your program, and also how you are running it. — Mark Costello
– Mark Costello, Commented Feb 18, 2013 at 22:59
You are returning from the for loops in your EhMensuravel functions. This means it will only ever use j = 0 and i = 0 (unless len(weights) is 0, in which case the function will return None as the inner loop will not run). — andersschuller
– andersschuller, Commented Feb 18, 2013 at 23:01
But how I can fix it? I think when I do return EhMensuravel(entry, weights[1:], final_weight) "weights[1:]" is also wrong, but I don't know how to fix it — user2083363
– user2083363, Commented Feb 18, 2013 at 23:12

wasserfeder · Accepted Answer · 2013-02-18 23:34:46Z

1

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.

answered Feb 18, 2013 at 23:34

wasserfeder

4962 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

aug2uag Over a year ago

note that wasserfeder did not implement an iteration when recursion was desired, and i don't think you can implement a recursion during an iteration, since the iteration is itself recursive

Collectives™ on Stack Overflow

Recursion in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related