Python Recursion List Sum of Pairs

Question

I am supposed to write two functions that do the exact same thing but their implementation is different.

The function takes as input a list of positive integers and a positive integer n, and returns True if two of the numbers in list equal to n. Otherwise, it returns False.

The first function is supposed to use a nested a loop, which I was able to get.

The second functions is not supposed to use a nested loop. However, you are supposed to sort the list out and then solve the problem.

Here is what I have for the second function.

def pairs2(lst, n):
    lst.sort()
    if len(lst) == 2:
        if lst[0] + lst[1] == n:
            return True
        else:
            return False
    elif len(lst) >= 3:
        for i in range(len(lst) - 1):
            if lst[0] + lst[i + 1] == n:
                return True
        lst.remove(lst[0])
        pairs2(lst, n)

The function works until the last two lines are implemented. After that, it doesn't return anything. What is wrong with my function?

Also, are they any other alternatives to that I do not use recursion? I just came up with using recursion since it was the first idea that I got.

I suspect you mean return pairs2(lst, n), instead of pairs2(lst, n), which just throws the recursively obtained result away.. — Blorgbeard
– Blorgbeard, Commented Aug 18, 2014 at 4:28

perreal · Accepted Answer · 2014-08-18 04:52:30Z

1

A recursive algorithm that eliminates the largest number at each recursive step:

def pairs2(lst, n, s=False): 
    if len(lst) < 2: return False
    if not s: lst = sorted(lst)
    for item in lst:
        if item + lst[-1] > n:  
            return pairs2(lst[:-1], n, True)
        if item + lst[-1] == n:
            print item, lst[-1]
            return True
    return False

The s parameter indicates whether the list is already sorted or not.

edited Aug 18, 2014 at 4:52

answered Aug 18, 2014 at 4:46

perreal

98.7k23 gold badges159 silver badges187 bronze badges

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

1 Comment

Burhan Khalid Over a year ago

As you have modified the function signature, I think explaining what s is used for would help.

Artjom B. · Accepted Answer · 2015-05-30 16:22:29Z

0

def pairs2(lst, n):
   [pair for pair in itertools.combinations(lst,2) if sum(pair) == n]

Instead of using recursion, you could use the brute-force approach to find the pairs using the itertools.combinations.

Read more about itertools: https://docs.python.org/2/library/itertools.html

edited May 30, 2015 at 16:22

Artjom B.

62k26 gold badges137 silver badges236 bronze badges

answered Aug 18, 2014 at 4:35

lakshmen

29.2k68 gold badges183 silver badges286 bronze badges

1 Comment

Burhan Khalid Over a year ago

This is great and everything, but I suspect the OP is doing an assignment, so without further explanation this answer is not really helping.

Collectives™ on Stack Overflow

Python Recursion List Sum of Pairs

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related