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

• Francis Avila: "Something is wrong." Please edit your question to say what is wrong.
• Mark Costello: Please share the output of your program, and also how you are running it.
• andersschuller: 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).
• user2083363: 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

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

• aug2uag: 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