Skip to main content
 首页 » 编程设计

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

2024年12月31日12java哥

我正在编写一个快速排序函数并使用递归来“分而治之”。我试图记录函数调用自身的次数。但是,我显然在递归概念上遇到了麻烦,因为我无法保存第二个值来保持计数。我试图将 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

请您参考如下方法:

您可以跟踪函数在每次递归调用中调用自身的次数,将它们相加并添加 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)