使用递归查找列表中第二小的数字

我知道有人就这个主题提出了问题，但没有一个答案对我有帮助。我不需要帮助实现代码，我只需要帮助对此递归过程进行排序。

我最初想在每个级别递归地返回一个元组并进行比较以找到第二小的值。但这不起作用，因为我希望我的函数最终只返回 1 个值 - 第二个最小值。

我将如何进行这个问题的递归过程？谢谢你！

编辑：抱歉没有包含足够的详细信息，所以就到这里。

函数应按如下方式工作：

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

第二次编辑：抱歉耽搁了，一直忙到现在，终于可以坐下来把我想到的写进代码了。它按预期工作，但老实说，我认为这是一种非常糟糕且低效的递归方式，因为你可能会说我对这个概念很陌生。

使用下面的伪代码重新表述我原来的问题：是否可以执行我在这里所做的操作，但不将其包装在第二个函数中？也就是说，是否有可能有一个函数仅递归调用其自身，并返回 1 个数字（第二小的数字）？

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]

您可以编写递归函数来接受 3 个参数：迄今为止遇到的第一个和第二个最小值，以及列表的其余部分（您尚未检查）。

然后，通过将列表参数的第一个元素与迄今为止最小的两个元素进行比较，您可以选择 3 个中的哪 2 个作为参数传递到下一个递归。

您需要将此递归函数包装在一个表示函数中，该函数设置并调用递归函数，同时处理元素少于 2 个列表等情况。

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)

这种解决方案并不是特别Pythonic——它更像是一种函数式编程风格。

最后，您可以传递列表前面的参数，并组合这两个函数来获得您正在寻找的解决方案：

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)

请注意，此函数做了一些多余的工作，因为它无法知道它是否首先被调用，或者是否递归地调用自身。还，+创建一个新列表，因此对于大小为 n 的列表，此代码可能需要 O(n^2) 时间。