Find the second smallest number in a list using recursion

Question

I know there has been a question asked on this topic, but none of the answers have helped me. I don't need help with implementing the code, I just need help sorting through the recursive process for this.

I was originally thinking recursively return a tuple each level and compare to find the second smallest value. But this doesn't work as I want my function to only return 1 value in the end- the 2nd smallest value.

How would I go about the recursive process for this problem? Thank you!

Edit: Sorry about not including enough details, so here goes.

Function should work as follows:

>>> sm([1,3,2,1,3,2])
>>> 2

Second edit: Sorry for the delay, I was busy until now, finally was able to sit down and put what I had in mind into code. It works as intended, but I honestly think this is a very shitty and inefficient way of doing recursion, as you can probably tell I am new to the concept.

To rephrase my original question using the pseudo code below: Is it possible to do what I did here, but without wrapping it in a second function? That is, is it possible to have a function that only recursively calls its self, and returns 1 number- the second smallest number?

def second_smallest(list):
    def sm(list):
        if base case(len of list == 2):
            return ordered list [2nd smallest, smallest]
        else:
            *recursive call here*
            compare list[0] with returned ordered list
            eg: [3, [5,2]]
            re-arrange, and return a new ordered list
            [3,2]
    return sm(list)[0]

Answer 1

You can write your recursive function to take 3 arguments: the first and second smallest values you've encountered so far, and the rest of the list, which you haven't inspected.

Then, by comparing the first element of the list argument with the two smallest-so-far, you can choose which 2 of the 3 to pass as the arguments to the next recursion.

You need to wrap this recursive function in a presentation function, which sets up and calls the recursive one, while handling cases like lists that have less than 2 elements.

def recurse(min1, min2, list):
    if len(list)==0:
        return min2
    first, rest = list[0], list[1:]
    if first < min1:
        return recurse(first, min1, rest)
    if first < min2:
        return recurse(min1, first, rest)
    return recurse(min1, min2, rest)

def second_smallest(list):
    if len(list) < 2:
        raise ValueError("too few elements to find second_smallest")
    a, b, rest = list[0], list[1], list[2:]
    if b < a:
        return recurse(b, a, rest)
    else:
        return recurse(a, b, rest)

This kind of solution isn't particularly Pythonic -- it's more of a functional programming style.

Finally, you can pass the arguments on the front of the list, and combine the two functions to get the kind of solution you're looking for:

def second_smallest(list):
    if len(list) < 2:
        raise ValueError("too few elements to find second_smallest")
    a, b = list[0], list[1]
    a, b = min(a,b), max(a,b)
    if len(list) == 2:
        return b
    c, rest = list[2], list[3:]
    if c < a:
        return second_smallest([c,a]+rest)
    if c < b:
        return second_smallest([a,c]+rest)
    return second_smallest([a,b]+rest)

Note that this function does some redundant work, because it can't know if it's being called first, or if it's calling itself recursively. Also, + creates a new list, so this code will likely take O(n^2) time for a list of size n.

Answer 2

You can use a flag to keep track whether you're in the most outer level of the calls.

def second_smallest(numbers, top_level=True):
    # Do your stuff and call `second_smallest(numbers[1:], False)` for any recursions.
    # When it comes to returning a value from the function, use the following.

    if top_level:
        return result[0]   # what your function ultimately returns
    return result          # [second, first] since you're still in recursive calls