# How does recursion works when there are 2 or more consecutive recursive calls?

I was learning about recursion and i came across the following pseudo code for quicksort.

QUICKSORT(A,p,r)
1   if p < r
2      then q := PARTITION(A,p,r)
3           QUICKSORT(A,p,q-1)
4           QUICKSORT(A,q+1,r)


In this code there are two consecutive statements that recursively call quicksort function. It confuses me. I want to know how these statements gets executed. Does the partition of left half of the array happens recursively or does both left and right of the array gets partitioned at the same time?

• Depends on the semantics of the language, of course.
– Raphael
Jun 5, 2016 at 11:03
• maybe some of this question relates to the concept of local variables and the stack. try learning how the code translates into those concepts. (there are some demonstrations of this around.) it does show how many sophisticated concepts are implicit even in mere pseudocode.
– vzn
Jun 5, 2016 at 14:13

Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other.

However, since the two recursive calls operate on disjoint sections of the array, you could, in principal, execute them in parallel.

• I just realized that the obvious answer (this one) is so obvious only because sequential execution has been hammered into our brains for decades. This may be the root of many problems with parallel programming, among other things.
– Raphael
Jun 5, 2016 at 11:03