Recursive function call in Python

Question

I am a beginner in Python and want to solve the following problem: Given a list of n integer numbers and an integer result the correct operators (+, -, *, /) shall be found that solve a corresponding simple math equation.

Example:
For numbers = [2, 3, 4, 1] and result=13 the following solution should be found:
2 + 3 * 4 - 1 = 13.

I wrote the following code which finds a solution for n=4 by doing a brute force approach with 3 nested for loops in which the operators are alternated. I struggle though, when I try to write an algorithm where n is arbitrary. Can this be solved with a recursive function call and if so how?

numbers = [2, 3, 4, 1]
result = 13
op = ['+','-','*', '/']

Found=0
for i in op:
    for j in op:
        for k in op:
            #Build string for left side of the equation: e.g. '2 + 3 + 4 + 1'
            exp = str(numbers[0]) + i + str(numbers[1]) + j + str(numbers[2]) + k + str(numbers[3])
            if eval(exp) == result:
                Found += 1
                if Found == 1:
                    print('Found Solution(s):')
                print(f'{numbers[0]} {i} {numbers[1]} {j} {numbers[2]} {k} {numbers[3]} = {result}')

if Found == 0:
    print('No solution found!')

Yes. Recursion mainly means to write code to slightly reduce a problem and let the reduced problem be solved by the recursive call until it is so simple that no deeper recursion is necessary. Try to write code for this. If you have a specific issue you can ask here with your code. — Michael Butscher
– Michael Butscher, Commented Nov 25, 2020 at 11:34

python_user · Accepted Answer · 2020-11-25 11:47:01Z

2

Not a recursive solution, not any efficient than yours, but this deals with any number of operations.

itertools.product is used to get what you want, if I can come up with an efficient recursive solution I will edit this.

from itertools import product

def check_result(numbers,result):
    op = ['+','-','*', '/']
    for i in product(op,repeat=len(numbers)-1):
        t=[None]*(len(numbers)+len(i))
        t[::2],t[1::2]=numbers,i
        t=[str(i) for i in t]
        expr=''.join(t)
        if eval(expr)==result:
            return 'Found'
    return 'Not Found'

print(check_result([2, 3, 4, 1],13)) # Found
print(check_result([2, 3, 4, 1,2],14)) # Found
print(check_result([2, 3, 4, 1,2,3,3,1,2],242)) # Not Found

answered Nov 25, 2020 at 11:47

python_user

7,2482 gold badges18 silver badges38 bronze badges

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

2 Comments

Timus Over a year ago

You beat me: I was about to hit the publish button and then your answer appeared :) (which is virtually identical to what I was about to propose).

user2390654 Over a year ago

Thanks for the quick reply, this is much appreciated!

Collectives™ on Stack Overflow

Recursive function call in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related