Help with recursive function

[Flames91]

Hi all, I'm fairly new to python and I'm stuck with a problem. What I'm trying to do is write a recursive function that takes a list of integers and returns true if the list contains a single pair of integers whose sum is negative, and false otherwise. For example:

[13, 9, 15, -10, 11] would return True, because 9 + -10 is a negative number

[12, 8, 9, 17, -3] would return False, because no single pair of integers added up would result in a negative number.

What I have so far:

def neg_sum(L):
    if len(L) == 2:
        if L[0] + L[1] < 0:
            return True
        else:
            return False
    else:

I'm not quite sure what to write after this, I know that if the list has a length of 2, then all you need to do is add the two elements, and you see if the sum is negative or positive. However, if the list is larger than 2, I have to make a recursive call, which is where I'm getting confused. Anyone have some tips?

[woooee]

Recursion = a function that calls itself and is along the lines of

def recursion_funct(list_in):
    print "list is now", list_in
    if len(list_in) > 1:
        recursion_funct(list_in[1:])
    else:
        return    ## out of entries in the list

test_list=[13, 9, 15, -10, 11]
recursion_funct(test_list)

First figure how to use a function that calls itself (maybe tests the first entry against all negative numbers and then return a list from each successive call, but then what do you do if there is a positive number after a negative number). You'll have to figure that out before you can start coding.

[TrustyTony]

Your base case is the case with less than two elements in sequence and you should return True if sum of two first ones < 0 or otherwise the result of calling function recursively with smaller of first two in sequence and the other elements.

[Flames91]

Thanks for the replies. I've made some progress on writing this code, however, I'm still having some problems...

def neg_sum(L):
    print (L)
    if len(L) == 2:
        if L[0] + L[1] < 0:
            return True
        else:
            return False
    else:
        if L[0] < L[1]:
            print (L[0])
            del(L[1])
            return neg_sum(L)
        else:
            print (L[1])
            return neg_sum(L[1:])
test = [1,6,7,-4,36,3,4]
neg_sum(test)

This gives me the following as a result:

[1, 6, 7, -4, 36, 3, 4]
1
[1, 7, -4, 36, 3, 4]
1
[1, -4, 36, 3, 4]
-4
[-4, 36, 3, 4]
-4
[-4, 3, 4]
-4
[-4, 4]

So what this code seems to be doing is when the list has a length greater than two, it compares L[0] with L[1]. If L[0] is smaller, it deletes L[1], and does a recursive call for L without L[1]. If L[1] is smaller, it deletes L[0]. Once it goes through the entire list, it's taking the smallest number in the list and comparing it to the final element in the list. In this case, its comparing -4 and 4, and since the length of the list is now 2, it runs my base case. Any tips on how I could fix this?

[TrustyTony]

You should also check the sum of two first numbers and return true if sum is less than 0. Your base case does not deal with list less than two long and it is destructive, you should copy list by slicing instead of deleting from original list. Better would be to return false in case of less than two items as the base case, like I said.

[woooee]

[13, 9, 15, -10, 11] would return True, because 9 + -10 is a negative number

You have to compare each number to all of the other numbers, not just side-by-side pairs. I would suggest that you sort the list in reverse order so all negative numbers are at the end, and send to a function to compare the first element with all others and return a list of "True". You can then remove the number tested and call the function recursively,

[TrustyTony]

Sorry, not True, woooee. I have recursion working perfectly like I said,

1) fail (return False or []) if length is less than 2
2) short cut by returning True (I am actually returning the pair to give more useful information) if sum of first two is negative
3) otherwise call recursively with slice copy of list without the bigger of two first ones

I would PM to you the code, but you have not PM enabled.

[arson09]

I'm just a beginner trying to learn, but since the problem says that its supposed to check any two numbers in a list that adds up to a negative not just consecutive numbers, wouldn't it work if a for loop was added?

[woooee]

I'm just a beginner trying to learn, but since the problem says that its supposed to check any two numbers in a list that adds up to a negative not just consecutive numbers, wouldn't it work if a for loop was added?

Yes and would be better as loops are almost always better than recursion IMHO, but the problem states that the program must use recursion.

[Flames91]

Alright I think I figured it out!

def neg_sum(L):
    if len(L) == 2:
        if L[0] + L[1] < 0:
            print (True)
        else:
            print (False)
    else:
        if L[0] + L[1] < 0:
            print (True)
        else:
            if L[0] <= L[1]:
                del(L[1])
                return neg_sum(L)
            else:
                return neg_sum(L[1:])

I do unfortunately have one small problem though. Whenever I try to create the list from an input, I keep getting errors. For example, I added this bit of code at the bottom:

test = input("Enter numbers: ")
neg_sum(test)

and this error message popped up:

Traceback (most recent call last):
  File "C:\Python31\h3problem1.py", line 18, in <module>
    neg_sum(test)
  File "C:\Python31\h3problem1.py", line 8, in neg_sum
    if L[0] + L[1] < 0:
TypeError: unorderable types: str() < int()

I tried to convert the input into a list, however I still got errors. Any thoughts?
EDIT: I also just realized I never put in when the list has a length less than two, I'll edit that now.

[TrustyTony]

OK, here is my version, as you got it to work:

def neg_pair(seq):
    if len(seq)<2:
        # not found, return [] which is one of the False values
        return []
    else:
        # return the pair making the negative sum (it can be used as True truth value) if found or recurse
        return seq[:2] if sum(seq[:2]) < 0 else neg_pair([min(seq[:2])] + seq[2:])


for t in ([], [13, 11, 15, 5, 11, -10], [12, 8, 9, 17, -3], [-3, 234, -1, 43, 3], [-10]):
    print(t)
    print(neg_pair(t))
    print('Found' if neg_pair(t) else 'Not found')
    print('\nNon-recursively:')
    for pair in ((a, b) for ind1, a in enumerate(t)
                        for b in  t[ind1+1:] if a + b < 0):
        print(pair)
        break
    print('\n')

Good point in my version is that it works with all sizes very simply, bad is that recursive call makes copy of the list each time. However your version destroys the original list in processing by del. You would be better off by doing secondary function which call the del using function with copy of the original list.

I changed the specification to return non-False found pair in place of True value and [], which is False value in case of pair not found.

BTW do you really want to return None for all invocations of your function, as function does not return anything in case recursion is not used.

[woooee]

test = input("Enter numbers: ")
neg_sum(test)

I tried to convert the input into a list, however I still got errors

How did you convert it to a list? You also have to convert the numbers to integers also. It is better to ask for one number at a time and use a try/except to convert to an int, and then append to the list.

[woooee]

Since 2 loops would be required to solve this, you can also use two recursive functions. The following code compares the first number to all other numbers in the list. You would then create a top level function that would pass the original list to this function and then call itself again recursively after deleting the first number, so the second number would then be compared to all other numbers in the list, etc. Note that this function uses a copy of the list. Lists are passed by reference, meaning that the address in memory is passed, so any changes to one list affects all references to the list. When passing a list to more than one function it is a good idea to use a copy of the list.

def test_numbers(this_list, found_list):
    print "  list_in =", this_list
    
    ## if out of numbers, just return found_list
    if len(this_list) > 1:
        print "     comparing", this_list[0], this_list[1]
        if this_list[0] + this_list[1] < 0:
            found_list.append([this_list[0], this_list[1]])
        del this_list[1]
        found_list = test_numbers(this_list, found_list)

    return found_list

test = [1,6,7,-4,36,3,4]
print test_numbers(test[:], [])   ## passes a copy of the list

[TrustyTony]

You need only single pass to find the smallest, which you can short cut immediately after you got negative sum for those. My non-recursive check was O(n**2) non-optimal, just for test simplest coding version.

Here near optimal non-recursive version:

def non_rec_neg_sum(seq):
    if len(seq)<2:
        # not found, return [] which is one of the False values
        return []
    smallest = seq[0]
    for new in seq[1:]:
        if smallest + new < 0:
            return smallest, new
        elif new < smallest:
            smallest = new
    return []

[Flames91]

Hey guys, I was able to work out the last few problems I had with my code, it works great now. Also, thank you all for helping me out, I really appreciate it!

[M.S.]

in python 2.x:

test = []
for i in raw_input("Enter numbers separated by a coma(,):").split(','):
    test.append(int(i))
neg_sum(test)

EDIT: sorry Moders, while I was posting, it got solved.

[arson09]

Yes and would be better as loops are almost always better than recursion IMHO, but the problem states that the program must use recursion.

It's not possible to just simply return the recursive call after a for loop?