Home > Software design >  Two calls inside a recursive function
Two calls inside a recursive function

Time:09-03

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
  • Related