我正在编写一个快速排序函数并使用递归来“分而治之”。我试图记录函数调用自身的次数。但是,我显然在递归概念上遇到了麻烦,因为我无法保存第二个值来保持计数。我试图将 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)
关于python - 保存递归函数的多个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54193024/