Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Algorithms: Sorting and Searching Sorting Algorithms Implementing Quicksort

Daniel Breen
Daniel Breen
14,943 Points
Posted by Daniel Breen
Daniel Breen
14,943 Points

Nothing Prevents The Return Statement From Executing. How does this work?

I worked through this on my own then made adjustments in C#. I'm running a test, but I'm noticing that the return statement is called multiple times. It returns an incomplete list. How Does this work? Specifically, the last section of the code

            sortedList.AddRange(Sort(lessThanPivot));
            sortedList.Add(pivot);
            sortedList.AddRange(Sort(greaterThanPivot));

            return sortedList; // This will be called multiple times

It seems like there should be more code to prevent the return from happening before all of the recursive calls have been made. Typically, recursion I've used returns the function/method rather than just calling it. Maybe a check to make sure the sub-lists have been emptied?

I'm not saying the code is wrong. I'm just saying that I don't understand why this works since the method is returned multiple times.

Here's the code:

https://repl.it/@djbreen7/QuickSort

Daniel Breen
Daniel Breen
14,943 Points
Daniel Breen
Daniel Breen
14,943 Points

I was definitely having a brain fart the day that I asked this. It's clear as day now. I got a little hung up on following the debugger and not paying close attention to the multiple levels of the return statement, which is really the nature of recursion.

Oh well. Sometimes you learn something technical, other times you learn not to overthink things.

1 Answer

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 68,457 Points
Chris Freeman
Chris Freeman
Treehouse Moderator 68,457 Points

Good question! Key idea is that the return is not reached before the recursion is done. 

            sortedList.AddRange(Sort(lessThanPivot));  // recursion starts here for lessThanPivot
            // after recursion on lessThanPivot continue below...
            sortedList.Add(pivot);
            sortedList.AddRange(Sort(greaterThanPivot)); // recursion continues here for greaterThanPivot
            // after recursion on greaterThanPivot continue to return statement

On the recursive call, the idea continues, then that the sub-sorts are completed before the return within the recursion is reached.

Post back if you have more questions! Good luck!!

Daniel Breen
Daniel Breen
14,943 Points
Daniel Breen
Daniel Breen
14,943 Points

Thanks. I was discussing this with some other devs too. I wasn't even realizing that the return was returning to the sub-calls before finally working its way back up to the initial call. Which is funny, because that's the definition of recursion. Oddly, I'd just never seen it done this way. I'm more familiar with recursion using return before the self-call as a means to prevent further progression:

public static int CountDown(int num)
{
    // Normally the base case and the recursive case are opposite this example, but to illustrate the point of returning to prevent further execution...
    if (num != 0) {
        Console.WriteLine(num);
        return CountDown(--num); // return the method to prevent further execution
    }

    return -1; // Only ever runs once
}