CODEWITHSUNDEEP
pythonrecursion
mazlor
mazlor

Reputation: 1895

recursive technique rather than lists technique in python

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

Upvotes: 1

Views: 139

Answers (3)

perreal
perreal

Reputation: 97938

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.

Upvotes: 2

jassinm
jassinm

Reputation: 7491

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

Upvotes: 2

abarnert
abarnert

Reputation: 365657

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.

Upvotes: 2

Related Questions