pythonrecursion

# Two calls inside a recursive function

I am a relatively new programmer.

I would like to learn why the quick_sort() is called twice recursively. According to my understanding the last line will not be executed.

This line should not be reachable: `quick_sort(array, pi + 1, high)`

``````# Function to perform quicksort
def quick_sort(array, low, high):
if low < high:

# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)

# Recursive call on the left of pivot
quick_sort(array, low, pi - 1)

# Recursive call on the right of pivot
quick_sort(array, pi + 1, high)
``````

Solution

• Recursive calls work no differently than simple function calls.

Consider this function `f`, which makes two calls, one to function `a` and one to function `b`:

``````def f(n):
if n > 0:
a()
print(n)
b()

def a():
print('  a')

def b():
print('  b')

f(7)
``````

When we call function `f`, it will first make the call `a()`, then when that call has finished, it will make the call `print(n)`, then when that call is finished, it will make the call `b()`. Output:

``````  a
7
b
``````

There is no distinction between recursive calls and non-recursive calls. A function call is always just a function call; a recursive call is just a function call in which the called function happens to have the same name as the calling function.

Here is an example:

``````def f(m, n, depth=0):
if m < n:
mid = (m + n) // 2
f(m, mid, depth+1)
print('  '*depth, mid)
f(mid+1, n, depth+1)

f(0,15)
``````

When we call function `f`, it will first make the call `f(m, mid, depth+1)`, then when that call has finished, it will make the call `print(' '*depth, mid)`, then when that call is finished, it will make the call `f(mid+1, n, depth+1)`.

Output:

``````       0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
``````