1
$\begingroup$

This is an example algorithm of a recursive insertion sort I'm trying to understand. I've have tried understanding this with the help of print statements (which I've commented).

def ins_sort_rec(seq, i):
    if i == 0:
        return 
    # print(f"{'    ' * i} starting at depth {i}")
    ins_sort_rec(seq, i-1) 
    j = i 

    while j > 0 and seq[j-1] > seq[j]:
        seq[j-1], seq[j] = seq[j], seq[j-1]  
        j -= 1
    # print(f"{'    ' * i} ending at depth {i}")

ins_sort_rec([3, 1, 2, 18, 14, 7], 5)

The print statements have given an output like so:

                 starting at depth 5
             starting at depth 4
         starting at depth 3
     starting at depth 2
 starting at depth 1
 ending at depth 1
     ending at depth 2
         ending at depth 3
             ending at depth 4
                 ending at depth 5

The problem I'm facing is visualizing the call stack. Doesn't it again call recursively again when the function is called from the call stack and when is the code after it executed.

Btw I'm self learner just getting started with data structures and algorithms and finding it difficult to understand recursive call (within a recursive call, as I see it).

Any advice that'll put me in the right direction for understanding recursive calls, especially if there is code after a recursive call will be truly appreciated.

$\endgroup$

1 Answer 1

0
$\begingroup$

Insertion sort relies on the previous $i-1$ elements to sort the $i$-th element. In your recursive algorithm, it starts at $5$th element, but it relies on the previous $5-1$ elements, going all the way to the first, which we can trivially sort by doing nothing, then going back up to the $5$th element again.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.