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)
CodePudding user response:
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