How do I repeatedly add numbers with different arithmetic operations using recursion?

Question

I've been stuck for quite some time as to how to use recursion to "rephrase" a code similar to this:

def evaluate_wo_pemdas(numbers, operator_sequence):
    operator_list = []
    for operator in operator_sequence:
        if operator == "+":
            operator_list.append(op.add)
        if operator == "-":
            operator_list.append(op.sub)
        if operator == "/":
            operator_list.append(op.truediv)
        if operator == "*":
            operator_list.append(op.mul)
    current = numbers[0]
    for x in range(len(numbers) - 1):
        operation = operator_list[0]
        operator_list = operator_list[1:]
        current = operation(current, numbers[1])
        numbers = numbers[1:]
    return current

The idea is to create a recursive code that adds the numbers up without the automatic built-in PEMDAS function in python, with [numbers, ...] and operator_sequence in the form of strings, using the operator module in python e.g [1, 2, 3, 4], ["/", "+", "*"]

This is my terrible, terrible attempt at it:

def evaluate_wo_pemdas(numbers, operator_sequence):
    if len(numbers) == 1:
        return numbers.pop()

    operator_list = []
    for operator in operator_sequence:
        if operator == "+":
            operator_list.append(op.add)
        if operator == "-":
            operator_list.append(op.sub)
        if operator == "/":
            operator_list.append(op.truediv)
        if operator == "*":
            operator_list.append(op.mul)

    current = numbers.pop()
    next_no = numbers.pop(1)
    operator_used = operator_list.pop()

    return operator_used(evaluate_wo_pemdas(current, next_no))

if anyone can enlighten and offer any thinking tricks to make recursions in general make more sense, that would be of great help. Thanks a bunch.

Answer 1

import operator as op

def evaluate_wo_pemdas(numbers, operator_sequence):
    print(numbers, operator_sequence)
    if len(numbers) == 1:
        return numbers.pop()

    operator = operator_sequence.pop(0)
    if operator == "+":
        operator_used = op.add
    elif operator == "-":
        operator_used = op.sub
    elif operator == "/":
        operator_used = op.truediv
    elif operator == "*":
        operator_used = op.mul

    current = numbers[0]
    next_no = numbers.pop(1)
    numbers[0] = operator_used(current, next_no)

    return evaluate_wo_pemdas(numbers, operator_sequence)

The trick to recursion is making sure that you have a base case and a recursive rule.

In this example, the base case is when len(numbers) == 1. There's only one number, so there are no operations to perform.

The recursive case involves taking the first two numbers, performing the first operation on them, and then calling again with the new (smaller) number and operation lists. (This type of left-associative list-collapsing operation is often called a "left fold.")

---

As the other answers have explained, this is not the optimal way to implement recursion. I was simply trying to make as few changes to the original source as possible, so as to make it easier to see how to get from there to here.

Answer 2

I would try to take better advantage of Python's data structures and syntax to avoid the repetitive ifstatements:

from operator import add, sub, truediv, mul

BINARY_OPS = {
    '+': add,
    '-': sub,
    '/': truediv,
    '*': mul,
}

def evaluate_wo_pemdas(numbers, operators):
    if operators:
        operator = BINARY_OPS[operators[0]]

        numbers = [operator(*numbers[:2]), *numbers[2:]]

        return evaluate_wo_pemdas(numbers, operators[1:])

    return numbers[0]

print(evaluate_wo_pemdas([1, 2, 3, 4], ['/', '+', '*']))

I originally wrote this with methods like .pop(0) and list replacement via indexing but changed it to be non-destructive on its arguments. If you can, you want to avoid surprising your caller by changing their variables as a result of your function call.

Of course, you really want to add some sanity tests to: make sure there are enough numbers; that the operator character extracted is in the dictionary; that you didn't just divide by zero; there is something in numbers before return the first item; etc.

Answer 3

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects -

def evaluate_wo_pemdas(numbers, operator_sequence):
  # ...
  return evaluate_wo_pemdas(numbers, operator_sequence)

In the other answer, see how it's recurring directly on the inputs? This is a red flag and indicates that something in ... must cause numbers or operator_sequence to change, otherwise this function call would recur indefinitely.

In functional style, we rely only on functions which always produce the same outputs for the same inputs. Watch how we call pop on x but each time we get a different result -

x = [1,2,3]
x.pop()
x.pop()

1
2

Imagine if sometimes when we wrote 5-1 it would answer 4 and other times it would answer 3. What a nightmare that would be! We can work with lists in a more functional way by avoiding the use of side-effecting functions like pop, and append. Destructuring assignment is the key -

x = [1,2,3]
(a, *b) = x
(c, *d) = x

print(a,b)
print(c,d)

We can destructure x many times and still get the same result each time -

1 [2,3]
1 [2,3]

And did you ever notice how pop raises an error if you try it on an empty list?

x = []
x.pop()

IndexError: pop from empty list

In functional style, we also have to be careful not to attempt to destructure and empty list. To write our program, we can use mathematical induction technique -

1. if there are less than two numbers, there is nothing left to compute, return the first number
2. (inductive) there are at least two numbers. if there are no operators, we cannot know which operation to apply. raise a runtime error
3. (inductive) there are at least two numbers and at least one operation. extract the first two numbers, a and b, the first operator, op, and compute an intermediate result using apply_operator. Recur on sub-problem of the result prepended to the remaining_numbers and the remaining_operators -

def eval_wo_pemdas(numbers = [], operators = []):
  if len(numbers) < 2:                          #1
    return numbers[0]
  elif not operators:                           #2
    raise RuntimeError("no operator specified")
  else:                                         #3
    (a, b, *remaining_numbers) = numbers
    (op, *remaining_operators) = operators
    result = apply_operator(op, a, b)
    return eval_wo_pemdas([result, *remaining_numbers], remaining_operators) 

This approach highlights another best practice. Writing sophisticated behaviours is a matter of combining several simple behaviours. Breaking a problem down into smaller parts makes it easier to write/test/reuse each part -

import operator

def apply_operator(op = "", m = 0, n = 0):
  if op == "+": return operator.add(m, n)
  if op == "-": return operator.sub(m, n)
  if op == "/": return operator.truediv(m, n)
  if op == "*": return operator.mul(m, n)
  raise RuntimeError("unsupported operator", op)

print(eval_wo_pemdas([1,2,3,4], ["/", "+", "*"]))

You can visualize the process as -

eval_wo_pemdas([1,2,3,4], ["/","+","*"])
eval_wo_pemdas([0.5,3,4], ["+","*"])
eval_wo_pemdas([3.5,4], ["*"])
eval_wo_pemdas([14], [])

14