Save multiple values of recursive function

Question

I am writing a quick sort function and using recursion to "divide and conquer". I am attempting to keep a running count of the number of times the function calls itself. However, I obviously am having trouble with the concept of recursion because I am unable to save a second value to keep a count. I have tried to format the input_string and loops as a tuple or dictionary but I believe I have a fundamental misunderstanding of how I should do this. How do I pass 2 values to my recursive function successfully?

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

I am using the quick sort function defined here: https://stackoverflow.com/a/18262384/5500488

Why not make a loops a global variable and increment it's count by 1 every time the function gets called, or you will be calling the quickSort function multiple times in your program? — Jay
– Jay, Commented Jan 15, 2019 at 5:20

blhsing · Accepted Answer · 2019-01-15 05:36:25Z

You can keep track of the number of times the function calls itself in each recursive call, sum them and add 2 (because the function calls itself twice in non-terminal condition), and in the terminal condition where the length of the input is 1, you should return 0 as the number of times the function calls itself:

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

so that quickSort('gehdcabf') returns:

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

Collectives™ on Stack Overflow

Save multiple values of recursive function

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related