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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
$\begingroup$

You use complete induction and prove two things: 1. The function is correct for the starting case (often i = 0 or i = 1). 2. If the function is correct for all cases with i < I, then it is also correct for the case i = I.

In your case, I assume that the code for i = 0 is correct (in that case there is nothing to do). Then you can assume that ins_sort_rec(seq, i-1) is correct, and you need to prove only that ins_sort_rec(seq, i) is correct under that condition. You don't actually need to understand how that works in detail.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.