How To Add Numbers Recursively Without a For Loop?

user_18359618 0
Viewed 55

Without using a For Loop, I need to recursively check if any two numbers in a list add to 0. If it does, it will return True, else, it will return False. For example, [12, 5, 10, -5, -9] returns true as 5 + -5 = 0. However, [12, 8, 10, -5] would return false, because no two numbers add to 0.

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

I'm sorry, I'm pretty new to coding but my thought process was this: I would add the first number in the list (L) to the next number. If the sum wasn't zero, I would move on to the next number. May I ask how I would get it so that I can add every single number in a list to each other recursively, and without a for loop...?

recursion python
2 Answers

The basic structure of your code is right, but as you noted, you need to test L[0] against every element in L[1:] before you can discard L[0] and move on to the recursive L[1:] call.

Using in with a list is iterative (it loops over each item in the list testing for equality), but it's not a for loop, so this seems valid:

def testForZero(L):
    if len(L) < 2:
        return False
    if -L[0] in L[1:]:
        return True
    return testForZero(L[1:])

If you weren't allowed to use in and can only use recursive looping and you can't define a recursive helper to implement in, it gets super tricky, but is still doable -- you can kind of "fork" the recursion by having one branch eliminate L[0] and a second branch that eliminates L[1] (while keeping L[0]):

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

If we add a print(L) to this we can see that every possible pair ends up in the L[0], L[1] positions:

>>> def testForZero(L):
...     print(L)
...     if len(L) < 2:
...         return False
...     if L[0] + L[1] == 0:
...         return True
...     return testForZero(L[1:]) or testForZero([L[0]] + L[2:])
...
>>> testForZero([12, 8, 10, -5])
[12, 8, 10, -5]
[8, 10, -5]
[10, -5]
[-5]
[10]
[8, -5]
[-5]
[8]
[12, 10, -5]
[10, -5]
[-5]
[10]
[12, -5]
[-5]
[12]
False
user_37997590

Both solutions in @Samwise's answer work but are inefficient, requiring time complexities of O(n^2) and O(2^n), respectively.

If you are allowed to use the data type of a set, you can achieve a time complexity of O(n) by storing into the set the first number of the given list in each recursion and testing the negative of the second number against the set. Use an index to access the current position in the list instead of slicing it to avoid increasing the time complexity. Since the in operator for a set is not iterative, it would safely satisfy your requirement for using true recursion:

def testForZero(L, i=0, seen=None):
    if len(L) - i < 2:
        return False
    if not seen:
        seen = set()
    seen.add(L[i])
    if -L[i + 1] in seen:
        return True
    return testForZero(L, i + 1, seen)
user_68909120
Related