implementation error in Python recursive expression-CodePudding

I'm solving the problem. You have to leave the last list, but the previous list is printed out again.

def merge(xs,ys):
  # xs, ys, ss = xs, ys, []
  xs, ys, ss = xs[:], ys[:], []
  while xs!=[] and ys!=[]:
    if xs[0] <= ys[0]:
      ss.append(xs[0])
      xs.remove(xs[0])
    else:
      ss.append(ys[0])
      ys.remove(ys[0])  
  ss.extend(xs)
  ss.extend(ys)
  return ss

accumulator = []
remain = []

def merge2R(xss):

    if len(xss)% 2 != 0 :
     OExcept = len(xss)-1 
     remain.append((xss[OExcept]))
     xss.remove(xss[OExcept])   
     

   
    if xss !=  []:           
     accumulator.append(merge(xss[0],xss[1]))
     xss.remove(xss[0])
     xss.remove(xss[0])   
     return merge2R(xss)

    else: 
     return accumulator   remain

The result comes out like this. How can I fix it?

>>> merge2R([[2],[1,3],[4,6,7],[5,8],[9]])
[[1, 2, 3], [4, 5, 6, 7, 8], [1, 2, 3], [4, 5, 6, 7, 8], [9]]

Desired result value:

>>> merge2R([[2],[1,3],[4,6,7],[5,8]])
[[1,2,3], [4,5,6,7,8]]
>>> merge2R([[2],[1,3],[4,6,7],[5,8],[9]])
[[1,2,3], [4,5,6,7,8], [9]]

CodePudding user response：

Your code was working, you just needed to reset accumulator and remain

def merge2R(xss):
    # Declare use of globals
    global remain
    global accumulator

    if len(xss) % 2 != 0:
        OExcept = len(xss)-1
        remain.append((xss[OExcept]))
        xss.remove(xss[OExcept])

    if xss != []:
        accumulator.append(merge(xss[0], xss[1]))
        xss.remove(xss[0])
        xss.remove(xss[0])
        return merge2R(xss)

    else:
        x = accumulator   remain
        # Must reset accumulator and remain
        accumulator = []
        remain = []
        return x

Because you initialise both arrays as empty, then append to them:

# Remain
remain.append((xss[OExcept])) 
# Accumulator
accumulator.append(merge(xss[0], xss[1]))

After you have finished with the data in those arrays (at end of function) you need to discard it:

accumulator = []
remain = []

The result of not discarding these arrays is evident when calling the function with the same argument multiple times:

print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))
print(merge2R([[2], [1, 3]]))

[[1, 2, 3]]
[[1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]