Question regarding recursive stack while deleting middle element from stack

Question

I have the running code to remove the middle element from stack, that's not an issue. Here is my code;

def insert(stack,temp,curr,n):
#print(curr,stack)
    if curr!=n//2:
       print(curr)
       stack.append(temp)
    #return
    return

def delete_middle(stack,n,curr):
    while len(stack)>0:
       temp=stack.pop()
       delete_middle(stack,n,curr+1)
       insert(stack,temp,curr,n)
    #print(stack)
       return stack

delete_middle([2,4,1,18,34],5,0)

My code is working fine. But I am trying to understand how does the recursive stack work. For example, we are doing recursive call to delete_middle() around 5 times(same as length of list, stack). Each time the pointer variable , curr is updated to point at the current element. As you can see last value of curr will be 5, but since the length of stack is 0, there is no more recursive call. And then the insert() function is called.

Interestingly if I look at the values of curr inside insert(), we obtain following output;

4
3
2
1
0

Why is that we don't see the first value of curr as 5 here? I will highly appreciate some feedback here.And can I get some thoughts on its time complexity? It seems to be O(N) where N is size of the stack. But I am bit rusty about it. Will appreciate some insight here. thanks

Answer 1

Edit:

The insert funcs will be executed only after the recursive funcs will use the empty stack.

START DELETE 0 [only one while loop executed]
START DELETE 1 [only one while loop executed]
START DELETE 2 [only one while loop executed]
START DELETE 3 [only one while loop executed]
START DELETE 4 [only one while loop executed]
START DELETE 5 [NO while loop executed because list is empty]
-------------------------
START INSERT iteration 4
END INSERT iteration 4
END DELETE 4
-------------------------
START INSERT iteration 3
END INSERT iteration 3
END DELETE 3
-------------------------
START INSERT iteration 2
END INSERT iteration 2
END DELETE 2
-------------------------
START INSERT iteration 1
END INSERT iteration 1
END DELETE 1
-------------------------
START INSERT iteration 0
END INSERT iteration 0
END DELETE 0

So, we have insert function (4) running first because the when the last delete_middle(5) is executed the list, stack, is empty and it doesn't run the insert function as stated:

while len(stack)>0:
   ...........
   insert(stack,temp,curr,n)

The above in delete_middle with n=5 will not be executed because len(stack)==0.

How does middle work:

#first executed  delete_middle([2,4,1,18,34],5,0)
def delete_middle(stack,n,curr):                            iteration 1
    while len(stack)>0:                     initial stack   [2,4,1,18,34]   
       temp=stack.pop()               stack after removal   [2,4,1,18]
       .....
       delete_middle(stack,n,curr+1) -> becomes: delete_middle([2,4,1,18],5,1) iteration 2
                                          while len(stack)>0:                     initial stack   [2,4,1,18]   
                                          temp=stack.pop()                  stack after removal   [2,4,1]
                                          .....
                                          delete_middle(stack,n,curr+1) > becomes: delete_middle([2,4,1],5,2) and so on until stack = [] (empty)
                                          .....
      (!) During these iterations insert(stack,temp,curr,n) is not executed because:

How does insert run:

  delete_middle([2,4,1,18,34],5,0)
    # Iteration 1
    #delete_middle(stack,     n, curr+1)
    delete_middle([2,4,1,18], 5,   1   )
    insert not executed!
      # Iteration 2
      delete_middle([2,4,1],5,2)
      insert not executed!
        # Iteration 3
        delete_middle([2,4],5,3)
        insert not executed!
          # Iteration 4
          delete_middle([2],5,4)
          insert not executed!
            # Iteration 5
            delete_middle([],5,5) # returns nothing because it does not enter the while loop
            insert not executed!
    Only from now -> each insert will be executed from inside delete_middle!
            insert 4
              insert 3
                insert 2
                  insert 1

About the time complexity:

Time complexity = time taken to build the final list;
                = (1 pop + 1 insert) * n
                = O(n)

In worst-worst-case perspective, you could say that the complexity is O(n) because reducing the list size by 1 element involves appending 1 element to the list, this because you have only one recursion per level.(while .. return indentation)

Although pop is O(1) and the list decreases each time (O(log n)), when each middle_delete is called your algorithm's running time increases with the size of the input data by executing (n-1) appends in total; appending the whole remaining list.

Some starting point.

---

END edit

Regarding your code, yes, it works, with some limitations if I may:

1. length of the target list must be odd
2. takes some extra unnecessary* criteria (curr,n) [unnecessary see last part]
3. function not "quite properly" executed

Explanations:

1. Try for yourself

2. End of answer (have patience with me :) )

3. For instance:

In your code:

while len(stack)>0:
   .....
   return stack

Basically, it seems that you return the first value of the while loop. Example:

c = 0
def func(d):
  while d < 5:
    d+=1
    return d

print(func(c))

The recursive effect is triggered by the clever usage of the None resulting func(insert) inside the while loop. It's like pulling the hand-break instead of the pedal. :)

Regarding your questions:

As seen bellow, (the middle func is executed + insert func) for each element.

delete middle iterion 0
--------------------------
temp 34 0
delete middle iterion 1
--------------------------
temp 18 1
delete middle iterion 2
--------------------------
temp 1 2
delete middle iterion 3
--------------------------
temp 4 3
delete middle iterion 4
--------------------------
temp 2 4
delete middle iterion 5
--------------------------
======================
insert iteration 4
curr:4, stack:[], temp:2,n:5
======================
insert iteration 3
curr:3, stack:[2], temp:4,n:5
======================
insert iteration 2
curr:2, stack:[2, 4], temp:1,n:5
======================
insert iteration 1
curr:1, stack:[2, 4], temp:18,n:5
======================
insert iteration 0
curr:0, stack:[2, 4, 18], temp:34,n:5
[2, 4, 18, 34]

Why is that we don't see the first value of curr as 5 here?

If you start (curr) from 0, you will see iterations from 4->0, while when initial curr is 1, iteration will be 5->1; thus 5 (N) delete func calls will be triggered.

3. I refactored your code a little with a simple logic:

If you have a targeted list [1,2,..,n-1,n] and if you want to remove the middle part using recursive funcs perhaps this approach might appeal to you:

Let's start with a 0 counter count = 0 for each element of the list the counter will be incremented by 1 count+=1

Now, to eliminate one element from each side (left, right) to get to the middle, we can say: if count is 0 or count is even remove the last item from the list, if not remove the first item thus the list looses one item per iteration.

if count == 0 and count % 2 == 0:
 target_list.pop(-1)
else:
 target_list.pop(0)

Then what if the list has an even number of items? Then we will include this scenario too: if len(target) == 2.

Also I suggest to use one little trick, the fact that default value for a function argument is only evaluated once, at the time that the function is defined.

what I mean by this? Check example for Common Mistake #1.

To include everything from above into a final func (O(N)) :

def eliminate_middle(target, count=0, beg_l=[],end_l=[]):
  print(count)                                    # O(N)
  if len(target) == 1:                            # if target has only one element
    return beg_l+sorted(end_l)

  else:

    if count == 0 or count % 2 == 0:

      if len(target) == 2:                        # case len(target) is Even 
        return beg_l+sorted(end_l)                #eliminates the two middle elements

      end_l.append(target.pop(-1))                #target loses last element
      return eliminate_middle(target,count+1)

    else:

      beg_l.append(target.pop(0))                 # target loses first element
      return eliminate_middle(target, count+1)

print(eliminate_middle([2,4,1,18,34]))