1

i have a function its name is positive_negative 

def positive_negative(list_changes):
    """ (list of number) -> (number, number) tuple

    list_changes contains a list of float numbers. Return a 2-item
    tuple where the first item is the sum of the positive numbers in list_changes and
    the second is the sum of the negative numbers in list_changes.

    >>> positive_negative([0.01, 0.03, -0.02, -0.14, 0, 0, 0.10, -0.01])
    (0.14, -0.17)
    """

i can write this function using list techniques as follow :

def positive_negative(list_changes):
    pos = sum([item for item in list_changes if item > 0.0])
    neg = sum ([item for item in list_changes if item < 0.0]) 
    return pos, neg

and that is a good solution. now my question is how to use the recursion techniques to solve the same function , i have tried the following code , but unfortunately there is something wrong . 

def positive_negative(list_changes):
    pos = 0.0
    neg = 0.0
    if len(list_changes)== 0:
        pos =+ 0.0
        neg =+ 0.0
        return pos,neg
    else:
        if list_changes[0] > 0.0 :
            pos =+ list_changes[0]
        else:
            neg =+ list_changes[0]
        positive_negative(list_changes[1:])


    return pos,neg

can you help me find what is my mistake and how to get the right recursive function.

thank you

Improve this question
2
  • 1
    As a side note, an even better way to solve the problem is with a generator expression instead of a list comprehension—just remove the square brackets, and the list version works exactly the same, except that it doesn't have to build the whole list just to pass it to sum, it builds it lazily. Commented Apr 3, 2013 at 23:54
  • thank you abarnert , valuable advise. Commented Apr 3, 2013 at 23:59

3 Answers 3

Reset to default
2

Your first problem is this:

pos =+ list_changes[0]

Python doesn't have an =+ operator. So, this is equivalent to:

pos = (+list_changes[0])

Since list_changes[0] is a number, and +n is the same as n for any number (except in certain edge cases which don't matter here), you're just replacing pos each time instead of adding to it.

You probably want this:

pos += list_changes[0]

But the fact that you're trying to use += at all is a more fundamental misunderstanding. Each instance of positive_negative on the stack has its own pos and neg values. These start at 0.0, then you add either 0.0 or list_changes[0] to them, then you call a function that doesn't affect them, then you return them. So, you're going to end up returning either 0.0, list_changes[0] or list_changes[0], 0.0; whatever comes later in the list will never affect the result.

If you want the recursive function call to add anything, you need to do something with its return value. Something like this:

def positive_negative(list_changes):
    if len(list_changes)== 0:
        return 0.0, 0.0
    else:
        pos, neg = positive_negative(list_changes[1:])
        if list_changes[0] > 0.0:
            pos += list_changes[0]
        else:
            neg += list_changes[0]
        return pos, neg

Of course this solution obviously isn't tail-recursive… but that doesn't matter, because Python doesn't do tail recursion optimization anyway. I think this is the closest solution to what you were trying to accomplish.

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

1 Comment

i know that recursion isn't a good option in Python , just wanted to learn how to use this way, i like this solution you have presented, thank you .
2

not using tail recursion:

import operator


def positive_negative_change(l):
    if not l:
        return (0.0, 0.0)

    if l[0] >= 0:
        return tuple(map(operator.add, (l[0], 0.0),
                         positive_negative_change(l[1:])))
    else:
        return tuple(map(operator.add, (0.0, l[0]),
                         positive_negative_change(l[1:])))

in python one would use a generator, or tail recursion... if you are into brushing up recursion just read the little schemer

Improve this answer

Comments

2

Using some accumulators (psum, nsum):

def positive_negative(list_changes, psum=0, nsum=0):
    if len(list_changes) == 0:
            return psum, nsum
    if list_changes[0] < 0:
            nsum += list_changes[0]
    else:
            psum += list_changes[0]
    return positive_negative(list_changes[1:], psum, nsum)

# and another version:
def positive_negative2(list_changes, psum=0, nsum=0):
    if len(list_changes) == 0:
            return psum, nsum
    if list_changes[0] < 0:
            return positive_negative(list_changes[1:], 
                            psum, nsum + list_changes[0])
    return positive_negative(list_changes[1:], 
                            psum + list_changes[0], nsum)

print positive_negative([0.01, 0.03, -0.02, -0.14, 0, 0, 0.10, -0.01])

Output

(0.14, -0.17)

As a side note, python does not do tail call optimization so be cautious when using recursion. The function above fails if your list has about 1000 items in it.

Improve this answer

5 Comments

This is really just simulating iteration with tail recursion (which is pointless in Python, which has iteration, and doesn't optimize tail recursion). It's certainly worth it for the OP to understand how this works, but it probably isn't what he wanted to do.
It's not that "using recursion is not advised", it's that using recursion to simulate iteration is not advised (and bending over backward to make sure your recursion is tail-recursive is pointless). There are plenty of naturally recursive problems where the recursion limit is more than deep enough. (And, of course, you can still use Python for learning about recursion as long as you stick within the limit.)
@abarnert, thanks for the comment. tail recursion is also favorable for clarity though.
In many cases, the non-tail-recursive version is a more direct translation of the mathematical or English-language definition of what you're trying to write, and in such cases it's usually clearer. But really, programmers need to be learn how to translate between iterative/tail-recursive, and between non-tail-recursive/tail-recursive, so this is definitely a useful answer.
this is really rich discussion , thank you guys , i am learning alot from you all .

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.