python - 我的分而治之算法有效，但我的代码没有返回值

Question

所以我正在尝试学习以正确的方式编写代码，并且正在阅读一本算法和数据结构书。作为向读者传授算法值(value)的练习的一部分(甚至在我们开始学习算法之前)，我正在解决一个编码练习问题，该问题将在 O(N) 时间内找到整数列表中的第 k 个最小整数。我避免寻找答案，因为我想自己解决它以锻炼大脑。不管怎样，我得到的代码主要是使用公认的笨拙的分而治之算法。
我不需要任何关于算法本身的帮助!!我只想知道我做错了什么，因为我能够打印输出，但返回它不起作用。

alg_list = [7, 10, 18, 3, 8, 11, 9, 15, 0, 14, 12, 16, 6, 5, 2, 13, 17, 4, 1, 19]

def kth_smallest(k, input_list):
  N = len(input_list)
  if N == k:
    input_list.sort()
    M = input_list[-1]
    print M  # used this to get some output to ensure the algorithm works at least
    return M #this is where Im confused.  Why no return?
  else:
    if N == 1:
        M = input_list[0]
        #print '2nd condition'
        return M
    elif N%2 == 0:
        M = input_list[N/2]
        #print '3rd condition'
    else:
        M = input_list[(N - 1)/2]
        #print '4th'
    list_small = [x for x in input_list if x < M]
    list_large = [x for x in input_list if x > M]
    if len(list_small) == k - 1:
        #print '5th'
        return M
    elif len(list_small) > k - 1:
        #print '6th'
        kth_smallest(k, list_small)
    elif (len(list_large) + len(list_small)) == (k - 1):
        #print '7th'
        return M
    elif (len(list_large) + len(list_small)) == k:
        #print '8th'
        new_list = list_large + list_small
        kth_smallest(k, new_list)
    else:
        #print '9th'
        kth_smallest(k, list_large)

kth_smallest(3, alg_list)

这里打印3，但是如果我注释掉打印语句，它不会返回3。我在这里返回值“M”做错了什么？再一次，我确信我对算法的糟糕尝试是糟糕的，但我在本书的开头，这个练习只是为了让读者思考，所以我现在对它很糟糕感到满意。我只想知道我在返回值时做错了什么。我假设它是我失踪的非常明显的东西。

谢谢!!

Answer 1

在函数 kth_smallest 中，在每次调用 kth_smallest 的左侧添加 return。

然后，在此函数之外，更改:

kth_smallest(3, alg_list)

收件人:

val = kth_smallest(3, alg_list)
print val

或者简单地说:

print kth_smallest(3, alg_list)