0

As an exercise, I was trying to make a script that would give me the sum of the items in a list but without using SUM or FOR/WHILE loops.

I ended up solving it with:

def addition(data, total=0):
    if data:
        total += data.pop()
        return total if data == [] else addition(data, total)

print(addition([1,2,3,1,2,1]))

This works well and returns '10', but my initial approach was:

def addition(data, total=0):
    if data != []:
        total += data.pop()
        addition(data, total)
    return total

print(addition([1,2,3,1,2,1]))

and this second bit of code returns '1' instead of '10'. I can't figure out why the two approaches aren't doing the same thing or even where the second example comes up with the '1' as it enters the final loop with data = [] and totals = 10, I'm guessing that I'm missing some rule regarding how variable scopes work?

(as explained in the answers below, it had nothing to do with variable scope so I changed the title to reflect the issue, for anyone happening on this in the future)

Improve this question
3
  • 1
    This is not really related to your question (which is well answered below), but I'd like to add that Python doesn't offer any benefit to tail recursion, so you could simplify your function a bit to be something like if data: return data.pop() + addition(data) with else: return 0 as the base case. You wouldn't need the total argument at all, since the actual addition happens with the return values. Commented Jul 17, 2017 at 14:20
  • hey @Blckknght, still a bit new and I think I was looking at recursion the wrong way but looking at your example, I think I got it now. I was looking at it more like a while loop, where every iteration would be processed linearly and the output of one loop would be the input to the next until the base case was reached to break the loop but, that's not the case in recursion, is it? It's more like unpacking the same expression within itself until a known base case is reached and then everything gets solved from the inner most nested expression outwards. Thank you, that helped Commented Jul 17, 2017 at 15:57
  • @Blckknght def fib(data): if data > 1: return fib(data-1) + fib(data-2) elif data == 1: return 1 else: return 0 print(fib(15)) yup, got the idea and I now totally understand why the return statements were also necessary Commented Jul 17, 2017 at 16:37

3 Answers 3

Reset to default
3

When you call total += data.pop() in a child function, the variable total is not changed in the calling function because integers are immutable.

Only the first element to be popped, 1, is added to total before the function returns. For it to do the same thing, you would want to replace addition(data, total) with return addition(data, total).

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

5 Comments

Tested, you are correct. I did not realize copies were being made when I was calling the function again.
To be clear, the variable data is not copied because it is a list, only total is.
@SzombatfalviHunorGellèrt uh.. I actually think that part of the answer is wrong. No copies are made: data = [1,2,3,1,2,1]; print(addition(data)); print(data) will print an empty list.
@kazemakase data is not copied, total is. Integers are immutable
@yinnonsanders Not even total is copied. Integers do not need to be copied because they are immutable. In fact, it's impossible to copy them.
2

When in doubt, always add print statements ;) 

def addition(data, total=0):
   if data!= []:
      total += data.pop()
      print("Total is " + str(total))
      addition(data, total)
   return total

addition([1,2,3]) returns: 

Total is 3
Total is 5
Total is 6
3

Do you see where the mistake is now? :) You don't do anything with the return value of addition(data, total) - this code does nothing to result. What you can do is return this value: 

def addition(data, total=0):
    if data!= []:
        total += data.pop()
        return addition(data, total) 
    return total

Let's analyse what this code does: If data is empty - return total - we added everything already, nothing to do. If data is not an empty list, it will pop an element from data, add this value to total and repeat the process with a shorter list. Convince yourself that this code does indeed what you want.

Improve this answer

Comments

2

The result is not related to variable scopes. Your first implementation returns the result of the recursive calls to addition. The second implementation does not. Thus, total is not updated after the first element.

def addition(data, total=0):
    if data != []:
        total += data.pop()
        # addition(data, total)  # return value not used; this line does not modify result
    return total  # total = 0 + first element

Both functions pop from the original list and therefore modify the input data. Consider an alternative like this:

def addition(data, total=0):
    if data:
        return addition(data[1:], total + data[0])
    return total
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.