python - 保存递归函数的多个值

Question

我正在编写一个快速排序函数并使用递归来“分而治之”。我试图记录函数调用自身的次数。但是，我显然在递归概念上遇到了麻烦，因为我无法保存第二个值来保持计数。我试图将 input_string 和 loops 格式化为 tuple 或 dictionary 但我相信我有一个根本性的误解我应该怎么做。如何成功将 2 个值传递给我的递归函数？

def quickSort(input_string, loops):
    string_list = list(input_string)
    less = []
    equal = []
    greater = []

    loops = list(loops)
    loops.append(1)
    if len(string_list) > 1:
        split_val = string_list[0]
        for i in string_list:
            if i < split_val:
                less.append(i)
            elif i == split_val:
                equal.append(i)
            else:
                greater.append(i)
        out = (quickSort(less, loops) + equal + quickSort(greater, loops)), loops
        return out

    else:
        return string_list

我正在使用这里定义的快速排序函数:https://stackoverflow.com/a/18262384/5500488

Answer 1

您可以跟踪函数在每次递归调用中调用自身的次数，将它们相加并添加 2(因为函数在非终止条件下调用自身两次)，并且在输入长度为 1 的终止条件，您应该返回 0 作为函数调用自身的次数:

def quickSort(input_string):
    string_list = list(input_string)
    less = []
    equal = []
    greater = []

    if len(string_list) > 1:
        split_val = string_list[0]
        for i in string_list:
            if i < split_val:
                less.append(i)
            elif i == split_val:
                equal.append(i)
            else:
                greater.append(i)
        sorted_less, count_less = quickSort(less)
        sorted_greater, count_greater = quickSort(greater)
        return sorted_less + equal + sorted_greater, count_less + count_greater + 2

    else:
        return string_list, 0

这样 quickSort('gehdcabf') 返回:

(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'], 10)