Python recursion challenge

Question

I am currently in an introduction to Python and computational theory class, and there was recently a difficult question on the midterm that I simply was not able to solve. It involves writing code for a program that adds numbers. I believe the question is supposed to use recursion. I don't remember how exactly the question was worded, but here is the basic idea.

Implement the multiadder(n) function, which takes in a nonnegative integer n and adds n arbitrary values together. Each value to be added must be written as a separate call. For example:

>>> multi_three = multiadder(3)
>>> multi_three(1)(2)(3)
6

>>> multiadder(5)(1)(2)(3)(4)(5)
15

The code must be written by filling in the blanks.

def multiadder(n):
    assert n > 0
    if _________________________ :
        return _________________________
    else:
        return _________________________

The topics we have covered in class are higher order functions, recursion, lambdas, and control statements. We are not allowed to use data structure like lists and sets, nor are we allowed to import anything.

Someone please help. It's the only problem I couldn't get on the test!

Answer 1

Try this:

def multiadder(n):
  assert n > 0
  if n == 1:
    return lambda t: t
  else:
    return lambda a: lambda b: multiadder(n-1)(a+b)

if __name__ == '__main__':
  print(multiadder(5)(1)(2)(3)(4)(5))

For n == 1, the result must be a function returning the input.

For n > 1, wrap the result of n-1, by adding input.

This also works for concatenating strings, and other accumulating operations:

>>> multiadder(3)('p')('q')('r')
pqr

Answer 2

You could do it like this, but it is almost unreadable. I hope the explanations are helpful:

def multiadder(n):
    assert n > 0
    if n == 0:
        return 0
    else:
        return (lambda f: lambda i, n, sm: f(f, i, n, sm))(
                    lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i)
                )(0, n, 0)

See it run on repl.it.

How it works

The return value consists of three major parts:

(lambda f: lambda i, n, sm: f(f, i, n, sm))

In short, this function assigns a name to a function, so it can be called recursively. In more detail: It takes a function f that must itself accept 4 arguments, of which the first should be a self-reference. The function that is returned here takes the three other arguments, and returns the recursive call of f.

Part two is the real core:

(lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i))

This is passed as argument to the first function above, making recursion possible. This function takes the 4 arguments mentioned above, and applies the specific logic:

• i is the number that must be added
• n is the number of values still expected after this one
• sm is the so far accumulated sum (excluding i)

Depending on whether more values are expected this function returns the final result (sm+i) or a function with one argument that will do the same as described here (recursion) with decreased n, and adapted sum.

Finally, the initial values are passed to the above:

(0, n, 0)

Meaning, we start with number 0 (dummy), n expected values, and a current sum of 0.

Note

As the recursion in the above code does not involve a call to multiladder, and the assertion really excludes the if condition to be true, we can do without that if...else:

def multiadder(n):
    assert n > 0
    return (lambda f: lambda i, n, sm: f(f, i, n, sm))(
                lambda rec, i, n, sm: sm+i if n == 0 else lambda j: rec(rec, j, n-1, sm+i)
            )(0, n, 0)

Answer 3

You could also define an internal auxiliary function (loop) which keeps track of the sum state (acc) as the counter state (n) decrements

def multiadder(n):
  def loop(acc,n):
    if n == 0:
      return acc
    else:
      return lambda x: loop(acc+x, n-1)
  return loop(0,n)

print(multiadder(3)(1)(2)(3)) # 6
print(multiadder(5)(1)(2)(3)(4)(5)) # 15

It's not nearly as elegant as DarkKnight's answer, but it might be easier for a beginner to conceptualize. In fact, this pattern is so useful and versatile that I use it to define almost all of my recursive procedures.

def some_recursive_func:
  def loop(...state_parameters):
    if base_condition:
      return answer
    else:
      return loop(...updated_state_variables)
  return loop(...initial_state_variables)

The only adaptation we made to this pattern is wrapping the recursive branch of the if expression in in lambda x: ... – this is because multiadd is meant to return functions until n returned functions have been applied.

---

One more, just for fun using the legendary Y-combinator. This probably doesn't meet the criteria provided by your instructor, but it's cool to see it nonetheless. Multiline lambdas in python are not really a thing so readability suffers a little bit.

U = lambda f: f(f)
Y = U (lambda h: lambda f: f (lambda x: h (h) (f) (x)))

multiadder = Y (lambda f: lambda acc: lambda n:
  acc if n == 0 else lambda x: f (acc+x) (n-1)
) (0)

print(multiadder(3)(1)(2)(3)) # 6
print(multiadder(5)(1)(2)(3)(4)(5)) # 15

Or you could still have defined multiadder using def syntax if you wanted

def multiadder(n):
  return Y (lambda f: lambda acc: lambda n:
    acc if n == 0 else lambda x: f (acc+x) (n-1)
  ) (0) (n)

It works the same way.

I highly encourage you to trace the evaluation step-by-step to understand how it works. There are some tremendous insights to be gained in understanding these higher-order functions.

Answer 4

At first it seemed liked multiadder needed two inputs for this to work, but the answer is quite straightforward. I wouldn't think an "Introduction to Python" class would need lamba functions and so on.

This is final answer:

def multiadder(n):
    assert n > 0
    if n == 1:
        return 1
    else:
        return n + multiadder(n - 1)

The graph below explains how it works for n = 4:

multiadder(4)
     |
 return 4 + multiadder(3)
                  |
               return 3 + multiadder(2) 
                               |
                            return 2 + multiadder(1)
                                             |
                                         return 1

So the final result for n = 4 ends up being 4 + 3 + 2 + 1 = 10.